2
$\begingroup$

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!

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

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$

$\endgroup$
  • $\begingroup$ Thanks a lot! Seeing it written out helps lot. I understand now! $\endgroup$ – Clangorous Chimera Jul 25 '16 at 0:53
  • $\begingroup$ 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. $\endgroup$ – Jorge Fernández Hidalgo Jul 25 '16 at 0:54
  • $\begingroup$ Oh, and happy to help. Please tell me if something is confusing. $\endgroup$ – Jorge Fernández Hidalgo Jul 25 '16 at 0:54
  • $\begingroup$ Good answer, but I think you want to modify your reference to Stirling numbers and to splitting balls into nonempty parts. $\endgroup$ – user84413 Jul 25 '16 at 1:58
  • $\begingroup$ why?${}{}{}{}{}{}$ $\endgroup$ – Jorge Fernández Hidalgo Jul 25 '16 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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