GATE Overflow Test Series | Discrete Mathematics | Test 2 | Question: 21

Question

The number of non-empty partitions of a set of size $5$ is $\_\_\_\_\_$

Answer 1

The number of non-empty partitions of a set of size $n$ (same as the number of equivalence relations on the set) is given by the $n^{th}$ Bell number denoted by $B_n$. We can use Bell triangle to derive $B_n.$ Bell number $B_n$ is given by the first number in the $n^{th}$ row (starting from 0) of the Bell triangle which can be formed by the following equation.

$E(i,j) = E(i,j-1) + E(i-1,j-1), j > 1$

$E(i,1) = E(i-1,i-1) = B_n$ (last entry in the previous row)

$E(0,0) = 1$

Thus, we can form the Bell triangle as

$\begin{array}{cccccc}
1 \\
1 & 2\\
2&3&5\\
5&7&10&15 \\
15&20&27&37&52\\
52
\end{array}
$

Thus, $B_5 = 52$

Comments

https://gateoverflow.in/2259/gate1997-6-3#c327234

refer this question to know more about bell triangle.

---

why is the answer not 51? as one of the partitions counted is {1,2,3,4,5} {} which is not a not null partition. Or this is not what it means?

---

@arjun sir shound’t it be mentioned that all elements are distinct

Answer 2

Different possible partitions are
5                              => one partition with five elements
4+1  ,       3+2         => two partitions with 4,1 or 3,2 elements
3+1+1   ,    2+2+1  => 3 partitions with  3,2  or 2,2,1 elements
2+1+1+1                 => 4 partitions with 2,1,1,1 elements
1+1+1+1+1            => 5 partitions with one elements each.

Now we just need to calculate the number of ways of placing the five elements of our set into these sized bins.
5 (one partition with 5 elements) = 5c5 = 1 way
4+1 = 5c4 = 5 ways
3+2  = 5c3 = 10 ways
3+1+1 = 5c3 = 10 ways
2+2+1 = 5c2 * 3c2 / 2! = 15ways
2+1+1+1 = 5c2  = 10 ways
1+1+1+1+1 = 1 way

total = 1+5+10+10+15+10+1 = 52 ways