Question

How many transitive relations are there on a set with n elements if

a)n=1   b) n=2  c) n=3

Comments

A={ } then no of transitive relations are 1.

A={1},no of transitive relations are 2.

A={1,2},no of transitive relations are 13.

A={1,2,3},no of transitive relations are 171.

A={1,2,3,4},no of transitive relations are 3994.

---

 

Number of transitive relations on n labelled nodes.   19

1, 2, 13, 171, 3994, 154303, 9415189, 878222530,...

Answer 1

https://en.wikipedia.org/wiki/Transitive_relation#Counting_transitive_relations

https://www.quora.com/How-do-I-find-number-of-transitive-relations-on-a-set

On the basis of given link,

There is No general formula to counts the number of transitive relations on a finite set.

a) n=1, number of transitive relations will be 2

b) n=2, number of transitive relations will be 13

There are direct formulas to count other types of relations.

No. of relations =2^mn

No. of reflexive relations =2 ^n(n-1)

No. of irreflexive relations = 2 ^n(n-1)

No. of symmetric relations = 2 ^n(n+1)/2

No. of asymmetric relations = 3 ^n(n-1)/2

No. of Anti Symmetric Relations = 2 ⁿ *  3 ^n(n-1)/2

I hope te answer is helpful :)

Comments

some correction in ans.
for n=2 it should be 13
and for n=3 it should be 171

---

case : n=1

 Let A={a}, then two relations are possible - empty relation and R={(a,a)}

Both are transitive, so answer must be 2.

---

For n=1 and n=2, its quite easy to list all relations out and then filter, but how you did it for n=3?

Answer 2

https://cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.pdf  Please refer to this paper. first take 2 elements (pair) at a time and then take 3 elements ata time in sequence to form transitive relation. 

Comments

a) If n = 1, then there is 1 transitive relation on the set.

b) If n = 2, then there are 3 transitive relations on the set.

c) If n = 3, then there are 14 transitive relations on the set.