# 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?

So the answer is

$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

## 3 Answers

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.

This answer is incorrect with the correct answer of 52. You must have double counted things though I'm not going through to check what. This problem is computing the 5th bell number. For more info http://mathworld.wolfram.com/BellNumber.html.

Otherwise your method is correct.

• As McFry pointed out in a comment, there are 15 partitions with pattern (2,2,1), not 30. – David K May 13 '16 at 20:20

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$