“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?

Solutions Collecting From Web of "“Probability” of a map being surjective"

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.