# Proof of ways to put distinct Balls into distinct Boxes

So I have learned that the formula for putting m balls into n boxes such that no box is empty is the following: $$T(m,n)=\sum_{k=0}^n (-1)^k{n \choose k}(n-k)^m$$ I am really confused as how to prove this. If someone could please explain it, I would much appreciate it!

• Please clarify your question. Putting m balls into n boxes such that ... – Behrouz Maleki Jul 25 '16 at 0:33
• You forgot to say no box can be empty, otherwise it would simply be $n^m$ – Jorge Fernández Hidalgo Jul 25 '16 at 0:35
• @CarryonSmiling Sorry. My bad! – Clangorous Chimera Jul 25 '16 at 0:37
• Apply Inclusion–exclusion principle. see en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle – Behrouz Maleki Jul 25 '16 at 0:38
• Given finite sets A and B, how many surjective functions (onto functions) are there from A to B? – Behrouz Maleki Jul 25 '16 at 0:40

## 1 Answer

This is the number of ways to split $m$ distinct balls into $n$ boxes so that no box is empty (or the number of surjections $f:\{1,2,\dots m\}\rightarrow \{1,2\dots n\}$).

The proof is a simple inclusion/exclusion proof.

Let $A_x$ be the set of functions that don't contain $x$ in the range.

We wish to find $n^m-|A_1\cup A_2\dots \cup A_n|$ (in other words, we want to count how many functions are not surjective).

Because of inclusion exclusion $|A_1\cup A_2\dots \cup A_n|=\sum\limits_{k=1}^n(-1)^{k+1}\sum\limits_{i_1<i_2\dots<i_k}|A_{i_1}\cap A_{i_2}\dots \cap A_{i_k}|$

Clearly $|A_{i_1}\cap A_{i_2}\dots \cap A_{i_k}|=(n-k)^m$ independently of the actual values of $i_1,i_2\dots i_k$.

So our sum is just $\sum\limits_{k=1}^n(-1)^{k+1}\binom{n}{k}(n-k)^m$

Just to finish as smoothly as possible:

$n^m-\sum\limits_{k=1}^n(-1)^{k+1}\binom{n}{k}(n-k)^m=\sum\limits_{k=0}^n(-1)^k\binom{n}{k}(n-k)^m$

• Thanks a lot! Seeing it written out helps lot. I understand now! – Clangorous Chimera Jul 25 '16 at 0:53
• Just to be clear, I don't think of it like this in my mind. In fact I had to look out the actual formulation for inclusion/exclusion in wikipedia. I always had a sort of vague idea of what it meant, but I always forget the actual correct way to state it. – Jorge Fernández Hidalgo Jul 25 '16 at 0:54
• Oh, and happy to help. Please tell me if something is confusing. – Jorge Fernández Hidalgo Jul 25 '16 at 0:54
• Good answer, but I think you want to modify your reference to Stirling numbers and to splitting balls into nonempty parts. – user84413 Jul 25 '16 at 1:58
• why?${}{}{}{}{}{}$ – Jorge Fernández Hidalgo Jul 25 '16 at 2:11