Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
This is an immediate consequence of the definitions of the Bell numbers and the multinomial coefficient. –  Phira May 14 '11 at 11:36
    
We defined the Bell numbers quite short as "B(0) := 1, B(n) for n $\geq$ 1 := the quantity of set partitions of $[n]$". $[n]$ is defined as $\{1,\cdots,n\}$. How do I combine that defintion and the one of the multinomial coefficient with the given formula? –  muffel May 14 '11 at 11:44
1  
I am struggling with this sum. Do you have a definition for $\sum_{a_1+...+a_k = n, \, a_k \geq 1}$ –  monoid May 14 '11 at 13:43
    
It means "sum over all tuples $(a_1,\dotsc,a_k)$ such that their sum is $n$ and they're all greater or equal to $1$". –  joriki May 15 '11 at 17:13
add comment

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
great, thank you for this explanation! –  muffel May 15 '11 at 17:06
add comment

We have $$B(n) = \sum_{k=1}^n {n\brace k}$$ and the bivariate generating function of the Stirling numbers of the second kind is $$G(z, u) = \exp(u(\exp(z)-1)).$$ Substituting this into the sum we get $$B(n) = \sum_{k=1}^n n! [z^n] [u^k] \exp(u(\exp(z)-1)) = \sum_{k=1}^n n! [z^n] \frac{(\exp(z)-1)^k}{k!}.$$ Observe that $$[z^n] \frac{(\exp(z)-1)^k}{k!} = \frac{1}{k!} \sum_{a_1+a_2+\cdots+a_k=n, a_i\ge 1} \frac{1}{\prod_{q=1}^k a_q!}$$ for a final answer of $$\sum_{k=1}^n n! \frac{1}{k!} \sum_{a_1+a_2+\cdots+a_k=n, a_i\ge 1} \frac{1}{\prod_{q=1}^k a_q!}$$ which is $$\sum_{a_1+a_2+\cdots+a_k=n, a_i\ge 1} \frac{1}{k!} {n\choose a_1,a_2,\ldots, a_k}.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.