Number of equivalence relations on a finite set

Question

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.

Answer 1

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.

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.

Answer 2

The number of ways of splitting a set of $n$ elements into $k$ classes is counted by the Stirling numbers of the second kind, the total number of equivalence relations is the $n$-th Bell number.

Answer 3

Every equivalence relation in a set induce a partition of that set into non-empty blocs and vice versa every set partition defines a equivalence relation on that set. Number of set partitions i.e number of equivalence relations on a n-set is called Bell number $B_n$.