[Math] Prove for Bell numbers

Question

I need to prove the following formula for Bell numbers:

$$ B(n) = \sum_{a_1 + \cdots + a_k = n, a_i \geq 1} \frac{1}{k!} \binom{n}{a_1 \cdots a_k} $$

Do you have any hint for me for getting this done?

Thank you in advance!

Answer 1

To count the number of partitions of $[n]$, you can go through all the ways of carving $n$ up into bin sizes $a_1,\dotsc,a_k$ that add up to $n$ and then count the number of ways of distributing $n$ objects into those bins, which is the multinomial coefficient. However, this overcounts, since if you swap two bins, you get the same partition, but you get a separate count in the sum. So you have to divide by the number of permutations of the $k$ bins, which is $k!$.

While this is the easiest way to get the factor of $k!$, it's also instructive to look at how different permutations of the bins are (over)counted in the sum. If you swap two bins of the same size, you get another distribution of the elements over the same bin sizes, so this overcounting is in the multinomial coefficient, so to speak. On the other hand, if you swap two bins of different sizes, you get a different arrangement of the same bin sizes, so this overcounting is in the sum, so to speak.