I have question

what is the no. of equivalence and transitive relations on a set of cardinality n?

my name is Siddhartha

I am a student of Computer Science at IIT, Kharagpur(INDIA)

Hi Siddhartha,

The number of equivalence relations on a set of cardinality n is the same as the number of partitions of the set. These are counted by what we call Stirling numbers of the second kind - S(n,i) is the number of ways to partition an n-set into i non-empty sets. S(n,i) may be obtained by an inclusion-exclusion argument and then you need to sum these up over i = 1 to n.


Go to Math Central