What's the expected number of empty boxes if we place k distinguishable balls into n distinguishable boxes?

Question

Harvard Statistics 110: see #30, p. 30 of pdf

Randomly, k distinguishable balls are placed into n distinguishable boxes, with all possibilities equally likely. Find the expected number of empty boxes.

I'm not convinced by the solution because, as illustrated by the picture of balls and boxes, there are $n^k$ different ways of filling the boxes by the balls, and there are $k$ different ways of one box being filled. One box can be filled by $1, 2, \dots k$ balls. Then, $P(I_j=0)=k/n^k$, and $P(I_j=1)=1-k/n^k$. But this will give weird results for $n=9, k=13$. I don't know but I feel there's something missing. May someone help?

Answer 1

The flaw in your reasoning is that there are many more than $k$ ways for a particular box to be filled.

Take the concrete example of $n=2$ boxes and $k=3$ balls. You are correct that there are $n^k=8$ different ways to fill the boxes. These $8$ ways can be enumerated by specifying the box where ball 1 lands, the box where ball 2 lands, and the box where ball 3 lands as a vector of three slots. The possibilities are: $$(1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2,1), (2,1,2), (1,2,2), (2,2,2).$$ Read $(1,1,1)$ as: "ball 1 lands in box 1, ball 2 lands in box 1, ball 3 lands in box 1". Let's focus on how box 1 can be filled or not filled. By inspection we see that there are $7$ ways for box 1 to be filled, not $3$, and in only one of these possibilities is box 1 empty. Moreover, $1 = (2-1)^3=(n-1)^k$; that is, the only way box 1 can be empty is if each ball lands in a box other than 1, which means each slot in the $3$-vector can be filled only with one of $n-1$ choices.

Answer 2

Consider there are k balls marked 1,2,3,4,.....k

and boxes marked as 1,2.....n

So to find the ways in which balls can be filled can be calculated as

1. When box 1 is filled with 1 ball. The no of ways in which this can happen is by choosing 1 ball out of k balls and then each remaining k-1 balls will have n-1 choices to go into n-1 boxes = $ \binom{k}{1}*(n-1)^{k-1}$

2. When box 1 is filled with 2 balls. The no of ways in which this can happen is by choosing 2 ball out of k balls and then each remaining k-2 balls will have n-1 choices to go into n-1 boxes = $ \binom{k}{2}*(n-1)^{k-2}$ ......... and so on.

3. till $ \binom{k}{k}*(n-1)^{k-k}$

Total no of ways to be filled = $\binom{k}{1}*(n-1)^{k-1} + \binom{k}{2}*(n-1)^{k-2} ..... + \binom{k}{k}*(n-1)^{k-k}$

$ = [\binom{k}{1}*(n-1)^{k-1} + \binom{k}{2}*(n-1)^{k-2} ..... + \binom{k}{k}*(n-1)^{k-k} + \binom{k}{0}*(n-1)^{k-0}] - \binom{k}{0}*(n-1)^{k-0}$

$ = (1+(n-1))^k - \binom{k}{0}*(n-1)^{k-0}$

$ = n^k - (n-1)^k$