Putting $n$ balls into n-1 cells such that no cell is empty

combinationscombinatoricsprobability

Suppose that $n$ identical balls are placed into $n − 1$ distinct boxes such that each distinguishable arrangement is equally likely. Find the probability that no box remains empty.

My answer is
$$ \frac{(n-1)(n-1)!}{(n-1)^n} $$
where the denominator is the total number of ways of putting $n$ balls in $n-1$ cells and the numerator is the number of ways $1$ ball can be put into $n-1$ boxes and then the remaining $n-1$ balls are put into $n-1$ boxes in $(n-1)!$ number of ways.

Is this correct? If not, why? The correct answer for this seems to be
$$ \frac{n-1}{\binom{2n-2}{n}}.$$

Best Answer

If no box is empty, one box must contain $2$ balls, and each of the other boxes must contain $1$ ball. There are $n-1$ ways to choose the box that gets $2$ balls, and after that everything is completely determined, so there are just $n-1$ distinguishable arrangements of the balls that have no empty box.

The remainder of the problem is counting all of the possible arrangements. That is a basic stars and bars problem, and the linked Wikipedia article has a decent explanation. Here you want Theorem two; the $k$ of the theorem is your $n-1$, and the $n$ of the theorem is your $n$, so the number of arrangements is

$$\binom{n+(n-1)-1}{n}=\binom{2n-2}n\;.$$