3
$\begingroup$

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?

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

4 Answers 4

8
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ As McFry pointed out in a comment, there are 15 partitions with pattern (2,2,1), not 30. $\endgroup$
    – David K
    Commented May 13, 2016 at 20:20
0
$\begingroup$

Number of equivalence relation on a set is equal to number of partition of that set containing n elements So number of partition of a set contains 5 elements is 52 ,hence it is total number of equivalence relation on this set ..

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .