# Number of equivalence relations on a finite set

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.

-
Do you mean the number of equivalence relations? (The maximum number of equivalent classes is $n$, which appears if you take equality as your equivalence relation.) – azimut Mar 6 '13 at 17:17
You are right. I mean if you have 3 equivalent classes, in how many ways can they be realized. I edited the question. – saadtaame Mar 6 '13 at 17:21

## 3 Answers

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.

-
I edited the question. I got it wrong at first. Thank you. – saadtaame Mar 6 '13 at 17:23
@saadtaame: ok. So I guess my post exactly answers your question. I'll edit to give some more details. – azimut Mar 6 '13 at 17:25
Isn't no. of partitions of a 2-element set = 3? {{a}}, {{b}}, {{a, b}}. How does the Bell number show 2 instead? – Masked Man Dec 25 '13 at 10:22
@Happy: Neither $\{\{a\}\}$ nor $\{\{b\}\}$ is a partition of $\{a,b\}$. The two partitions of $\{a,b\}$ are given by $\{\{a\},\{b\}\}$ and $\{\{a,b\}\}$. – azimut Dec 25 '13 at 13:23
Oh, right, I get it now. Thanks for that clarification. – Masked Man Dec 25 '13 at 15:21

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.

-

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

-