equivalence relaton

Question

How many different equivalence relations with exactly three equivalence classes are there on a set with 5 elements

1. 10
2. 15
3. 25
4. 30

Comments

The Bell numbers satisfy $B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_{k}$

$B_{5} = \binom{4}{0}.1 + \binom{4}{1}.1+\binom{4}{2}.2+\binom{4}{3}.5+ \binom{4}{4}.15   $

$B_{5} = 1 + 4 + 12 + 20 + 15$

$B_{5} = 52 $

---

5 elements can be divided into 3 partitions by 2 ways {1|1|3} and {2|2|1}

this problem is distinct objects to identical boxes

for {1|1|3} we have 2 boxes of size 1 and one box of size 3 
ways to select 5 objects to fill boxes with size 1 = $\binom{5}{2} = 10$

for {2|2|1} we have 2 boxes of size 2 and one box of size 1
 ways to select 5 objects to fill boxes with size 2 = $\binom{5}{4} = 5$
and these 4 objects can be arranged in 2 identical boxes of size 2 in 3 ways 

So 10 + 3*5 = 25

---

But bell numbers are used when you need to calculate the number of ways to put n indistinguishable balls in k identical bins when you can have the bin empty!

 

Dont you think?

Answer 1

• One Euivelence relation creates one partition.
• S = $\left \{ a,b,c,d,e \right \}$ ,here one possible parition is = $\left \{ \left \{ a,b \right \} , \left \{ c,d \right \} , \left \{ e \right \} \right \}$ . Tis partition has 3 groups. Corresponding EQ relation has 3 EQ classes. Note that this partition is unordered..
• So, no of different unordered partitions = No of equivalence relations.

Here the condition is we need only 3 equivalence classes. So, the partition has to be done in 3 unordered groups.

$$\begin{align*} \frac{5!}{1!1!3!}.\frac{1}{2!} + \frac{5!}{2!1!2!}.\frac{1}{2!} = 10 + 15 = 25 \\ \end{align*}$$ 

In case if we need maximum possible EQ relations on 5 elements.

$\begin{align*} 5 &\rightarrow 5\Rightarrow \frac{5!}{5!} = 1\\ \\ \hline \\ &\rightarrow 4 \qquad 1 \Rightarrow \frac{5!}{4!1!} = 5 \\ \\ \hline \\ &\rightarrow 3 \qquad 2 \Rightarrow \frac{5!}{3!2!} = 10 \\ \\ \hline \\ &\rightarrow 3 \qquad 1 \qquad 1 \Rightarrow \frac{5!}{3!1!1!}*\frac{1}{2!} = 10 \\ \\ \hline \\ &\rightarrow 2 \qquad 2 \qquad 1 \Rightarrow \frac{5!}{2!2!1!}*\frac{1}{2!} = 15 \\ \\ \hline \\ &\rightarrow 2 \qquad 1 \qquad 1 \qquad 1 \Rightarrow \frac{5!}{2!1!1!1!}*\frac{1}{3!} = 10 \\ \\ \hline \\ &\rightarrow 1 \qquad 1 \qquad 1 \qquad 1 \qquad 1 \Rightarrow \frac{5!}{1!1!1!1!1!}*\frac{1}{5!} = 1 \\ \\ \hline \\ &\Rightarrow \text{Total} = 1+5+10+10+15+10+1 = 52 \end{align*}$

The procedure for partitioning is , indistinguishable $\rightarrow$ indistinguishable but because of the distinct elements we need to further evaluation.

Graphically we were interested in the rectangle shown below containing 25 EQ relation or partitions.

Comments

This is also Bell Number for maximum case, right ?

---

yes :) $B_5$

---

thanks for ur detailed ans  , but why u have divided it by 2! in case of 3 1  1   and 2  2  1   

and by 3!  in  2   1   1   1 and so on

---

if we have a set {a,b,c,d} and two indistinct boxes

To allocate {a,b,c,d}...two-and-two,  in those two boxes we have only 3 choices. $\frac{4!}{2!2!}*\frac{1}{2!} = 3$

those are $\left \{ \left \{ a,b \right \} ,\left \{ c,d \right \} \right \} , \ \left \{ \left \{ a,c \right \} ,\left \{ b,d \right \} \right \} , \ \left \{ \left \{ a,d \right \} ,\left \{ b,c \right \} \right \}$

No need to put a in box2 and count again. because boxes are indistinct.

In analogy to these boxes, those groups of a partition are also same,only the elements inside a group are distinct.

Answer 2

http://www.geeksforgeeks.org/count-number-of-ways-to-partition-a-set-into-k-subsets/