Proof of ways to put distinct Balls into distinct Boxes

Question

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!

Answer 1

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$