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?