# “Probability” of a map being surjective

What is the probability of randomly putting $n$ elements into $k$ boxes ($k\leq n$) such that there is no empty box?

I have two different ideas:

• I could use the principle of inclusions and exclusions with $A_i=\{\text{box$i$is empty}\}$: \begin{align}P(\text{no empty boxes})&=1-P\left(\bigcup_{i=1}^k A_i\right)=1-\sum_{i=1}^{k-1} (-1)^{k-1} \binom{k}{i}\left(\frac{k-i}{k}\right)^n\\&=\sum_{i=0}^{k-1}(-1)^k\binom{k}{i}\left(\frac{k-i}{k}\right)^n\end{align}
• There are $\binom{n+k-1}{k-1}$ different ways of putting $n$ elements in $k$ boxes. Putting the elements in such that no box remains empty should be the same as putting $n-k$ elements in $k$ boxes i.e. $\binom{n-1}{k-1}$. So the probability that no box is empty should be \begin{align}P(\text{no empty boxes})&=\frac{\binom{n-1}{k-1}}{\binom{n+k-1}{k-1}}\end{align}

The two solutions are different. I'm pretty sure the first on is correct. Where is the mistake in the second one? Is the problem that the different ways of putting the elements in the boxes are not equal-probable? Can I fix the second attempt somehow?

-
I don't follow you on some things in the second approach. If we have 10 boxes and 12 things, how is putting the things in so none are empty analagous to puttint $n-k=12-10=2$ things into 10 boxes? I think you're assuming that during the first ten placements the bins get filled, and then you put the remaining two somewhere. But I'm not seeing why you can assume that the boxes get filled as soon as possible. And I also don't see your n-1 choose k-1 as being the number of ways to put n-k things into k boxes. – coffeemath Oct 21 '12 at 4:49
In the second approach I ignore the order, the elements get put in (may be that's the problem, why the different ways are not equal-probable). So I'd argue putting 12 elements in 10 boxes with the constraint, that all boxes get filled, is the same as putting 2 elements in 10 boxes. The number of ways of doing is is $\binom{n-1}{k-1}=\binom{11}{9}$ since I can view the ten boxes as $9$ barriers and putting 2 elements in 10 boxes as choosing 9 barriers out of $2+9=11$ elements. – Julian Oct 21 '12 at 7:13

To see what’s wrong with the second approach, look at the case $n=k=2$. Call the $2$ objects $a$ and $b$. The $4$ equally likely outcomes are:

$$\begin{array}{c|c} \text{Box }1&\text{Box }2\\ \hline a,b\\ a&b\\ b&a\\ &a,b \end{array}$$

Clearly the desired probability is $\frac12$.

When you say that there are $\binom{2+2-1}{2-1}=3$ possible distributions of the $2$ objects amongst the $2$ boxes, you’re talking about indistinguishable objects: the second and third cases in the table above are counted as a single distribution of the objects. The appropriate table is now this one, in which only one of the three distributions has objects in both boxes.

$$\begin{array}{c|c} \text{Box }1&\text{Box }2\\ \hline x,x\\ x&x\\ &x,x \end{array}$$

Your second calculation gives the probability that a randomly selected distribution of $n$ indistinguishable objects amongst $k$ boxes has no empty boxes.

In your case the objects being distributed really are distinguishable: there’s a difference between the identity function on $\{0,1\}$ and the function $f(x)=1-x$, though both are surjective. Your second calculation, however, treats these as the same function: each puts one object in each of the two boxes, so to speak.

-
Thank you! I think I got it. So the first calculation is correct? – Julian Oct 21 '12 at 18:20
@Julian: You’re welcome. Yes, it looks okay. (And even if I missed some minor algebraic error, the method is definitely okay.) – Brian M. Scott Oct 21 '12 at 18:24