# How many equivalence relation can be defined on a set of $5$?

The question is how many equivalence relation can be defined on a set of $5$?

I think this is asking how many different ways can we partition a set of $5$, right?

$1$ way: $$\{1\},\{2\},\{3\},\{4\},\{5\}$$

$_5C_2$ ways: $$\{1,2\},\{3\},\{4\},\{5\}$$

$_5C_2\times _3C_2$ ways: $$\{1,2\},\{3,4\},\{5\}$$

$_5C_3$ ways: $$\{1,2,3\},\{4\},\{5\}$$

$_5C_3$ ways: $$\{1,2,3\},\{4,5\}$$

$_5C_4$ ways: $$\{1,2,3,4\},\{5\}$$

$1$ way: $$\{1,2,3,4,5\}$$

So the total number is $1+10+30+10+10+5+1=67$.

Is that correct?

• Yes. This is correct. – OrangeApple3 May 13 '16 at 20:10
• Is there a closed formula for this instead of the silly method of counting. Especially when the size of the set becomes large? – velut luna May 13 '16 at 20:12
• As far as I know, there aren't any nice closed formulas. There are plenty of recursive formulas though. – OrangeApple3 May 13 '16 at 20:13
• You've counted each (2,2,1)-partition twice. There are only 15, not 30. – Anon May 13 '16 at 20:15
• @McFry You are correct. Thanks! Can you post it as an answer so that I can accept it? – velut luna May 13 '16 at 20:19

You've made a calculation error, you have double-counted the partitions of type $\{a,b\},\{c,d\},\{e\}$, since $\{a,b\},\{c,d\},\{e\}$ is the same partition as $\{c,d\},\{a,b\},\{e\}$. There are only $15$ of those, not $30$. The correct number of partitions (therefore also the correct number of equivalence classes) is $52$, the $5$th Bell number.
Yes,since each equivalent relation on a set yields a partition of that set in disjoint equivalence classes, for a finite set, the number of equivalence relations is the number of partitions, i.e. the n-th Bell number for a set of size n. Your calculation, however, is not correct: if $B_{n}$ is the number of partitions on a set of size n, notice $B_{n+1}=\sum_{k=0}^{n}C_{n}^{k}B_{k}$, and $B_{0}=1$. It is then easy to check that $B_{5}=52$