in Set Theory & Algebra
30,703 views
5 votes
5 votes
How many transitive relations are there on a set with n elements if

a)n=1   b) n=2  c) n=3
in Set Theory & Algebra
30.7k views

2 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.
1
1
 
Number of transitive relations on n labelled nodes.   19
  1, 2, 13, 171, 3994, 154303, 9415189, 878222530,... 
0
0

2 Answers

9 votes
9 votes
Best answer

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 =2mn

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 n *  3 n(n-1)/2

I hope te answer is helpful :)

edited by
by

3 Comments

some correction in ans.
for n=2 it should be 13
and for n=3 it should be 171
3
3
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.
4
4
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?
0
0
0 votes
0 votes

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. 

1 comment

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.
0
0

Related questions