n balls are thrown indepently into n boxes. What is the probability there is exactly one box empty?

Question

I am struggling to count the total number of possible outcomes, I assume it is easier to count the outcomes ignoring the order of the balls and the numbering of the boxes?

Answer 1

Exactly one ball must be thrown into a box where allready one ball is present. This cannot happen of course with the first ball. The probability that this happens with the $k+1$-th ball is: $$\frac{n}{n}\frac{n-1}{n}\cdots\frac{n-k+1}{n}\frac{k}{n}\frac{n-k}{n}\cdots\frac{2}{n}$$ This for $k=1,\dots,n-1$.

Do you understand why?

Addition of these probabilities gives you the answer to your question.

Answer 2

Hint: to get exactly one bin empty, you can arrange the balls one per bin, then move one ball to another bin. How many different ways are there to get the same final configuration?

Answer 3

Simple Method

For each of the $n!$ permutations of the $n$ balls into $n$ buckets, and a given pair of balls, there is another permutation that swaps the given pair of balls. These two permutations and this pair of balls define two unique arrangements where one bucket is empty: one where each element of the pair is moved to the other's bucket. Thus, we get $$ \binom{n}{2}n!\tag{1} $$ arrangements with one bucket empty. There are $n^n$ arrangements of the $n$ balls into $n$ buckets, giving a probability of $$ \binom{n}{2}\frac{n!}{n^n}\tag{2} $$

---

Inclusion-Exclusion

We can also use the formula for Generalized Inclusion-Exclusion derived in this answer to get the count in $(1)$.

Let $S(j)$ be the number of arrangements with bin $j$ empty. Then the sum of the sizes of the intersections of $k$ of the $S(j)$ is $$ N(k)=\binom{n}{k}(n-k)^n\tag{3} $$ The number of elements in exactly $1$ of the $S(j)$ is $$ \sum_{k=0}^n(-1)^{k-1}\binom{k}{1}\binom{n}{k}(n-k)^n\tag{4} $$ Using the defining identity for Stirling numbers of the Second Kind $$ \newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}} \sum_{k=0}^n\stirtwo{n}{k}\binom{x}{k}k!=x^n\tag{5} $$ we get $$ \begin{align} &\sum_{k=0}^n(-1)^{k-1}\binom{k}{1}\binom{n}{k}(n-k)^n\\ &=n\sum_{k=0}^n(-1)^{k-1}\binom{n-1}{k-1}(n-k)^n\tag{6a}\\ &=n\sum_{k=0}^n(-1)^{n-k-1}\binom{n-1}{k}k^n\tag{6b}\\ &=n\sum_{k=0}^n\sum_{j=0}^n(-1)^{n-k-1}\binom{n-1}{k}\stirtwo{n}{j}\binom{k}{j}j!\tag{6c}\\ &=n\sum_{k=0}^n\sum_{j=0}^n(-1)^{n-k-1}\binom{n-1}{j}\stirtwo{n}{j}\binom{n-1-j}{k-j}j!\tag{6d}\\ &=n\sum_{k=0}^n(-1)^{n-k-1}\stirtwo{n}{n-1}\binom{0}{k-n+1}(n-1)!\tag{6e}\\[4pt] &=\stirtwo{n}{n-1}n!\tag{6f}\\[6pt] &=\binom{n}{2}n!\tag{6g} \end{align} $$ Explanation:
$\text{(6a)}$: $\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$
$\text{(6b)}$: $\binom{n}{k}=\binom{n}{n-k}$ then change variables $k\mapsto n-k$
$\text{(6c)}$: apply $(5)$
$\text{(6d)}$: $\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$
$\text{(6e)}$: $j=n$ is removed by $\binom{n-1}{j}$ and $j\lt n-1$ is removed since $\sum\limits_{k=0}^n(-1)^k\binom{n}{k}=0$ for $n\gt0$
$\text{(6f)}$: $\binom{0}{k-n+1}$ removes all but $k=n-1$
$\text{(6g)}$: $\stirtwo{n}{n-1}=\binom{n}{2}$