I need a hint for computing the number of ways in which all the equivalent classes on a set of $n$ elements can be realized. For example, if the set has 2 elements ${a,b}$, then there are 2 possible partitions: either a and b are related or not.
[Math] Number of equivalence relations on a finite set
combinatoricsdiscrete mathematicsequivalence-relationsrelationsset-partition
Best Answer
An equivalence relation uniquely corresponds to a partition of the base set. For a fixed size $n$ of the base set, the number of such partitions is known as the Bell number $B_n$, see Wikipedia and the Online encyclopedia of integer sequences.
The first Bell numbers are $$1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, \ldots$$ The numbers are growing rapidly. Also, note that no simple closed formula for $B_n$ is known.