# Putting $n$ balls into $n$ boxes, what is the expected value of the number of balls that are in the right boxes?

I have the following probability question, with two different solutions, and I would like to determine which one is right. Here is the problem:

$$n$$ balls are labeled $$1$$ to $$n$$, and $$n$$ boxes are also labeled $$1$$ to $$n$$. Now put these $$n$$ balls randomly into these $$n$$ boxes, such that each box contains only one ball. If a ball is in the box with the same number it has (e.g. ball #3 is in box #3), then we say that this ball is in the right box. Let $$X$$ be the number of balls that are in the right boxes, what is the expected value of $$X$$?

Here are the two solutions I have:

Solution 1: The probability that at least $$k$$ balls are in the right box is $$P(X\ge k)=\frac{\binom{n}{k}(n-k)!}{n!}=\frac{1}{k!},\quad k=0,1,2,\dots,n,$$ so the expected value of $$X$$ is

$$E(X)=\sum_{k=0}^n P(X\ge k)=\sum_{k=0}^n\frac{1}{k!}.$$

Solution 2: For $$j=1,\dots,n$$, let $$X_j$$ be the random variable such that $$X_j=\begin{cases}1, &\text{if ball }\#j\text{ is in the right box},\\ 0, &\text{otherwise},\end{cases}$$ Then we have $$X=\sum_{j=1}^n X_j$$. For each $$j=1,\dots,n$$, we have $$P(X_j=1)=\frac{(n-1)!}{n!}=\frac{1}{n},$$ therefore, $$E(X)=\sum_{j=1}^n E(X_j)=1.$$

From my instinct, I feel that the first solution is the right one, but I cannot tell what is wrong with the second solution (Maybe I am wrong?). Any suggestions would be greatly appreciated!

Edit: Now I've figured out that the second one is right. The problem with the first one is that the relation $$P(X\ge k)=\frac{\binom{n}{k}(n-k)!}{n!}$$ is incorrect, and thus caused the wrong answer.

• The second is the correct one. I don't quite get the probability calculation in the first. It is impossible to have only one incorrect, so $P(X=n-1)=0$, and your probability is not compatible with that. Nov 1, 2022 at 8:57
• $P(X\ge 1)\neq\frac{1}{1!}=1$ Nov 1, 2022 at 8:58
• @JaapScherphuis I see, this makes sense. Thanks! Nov 1, 2022 at 9:00
• @DanielMathias Thanks. Now I see where the mistake is. Nov 1, 2022 at 9:00

The second solution is the right one. What was your thinking process when claiming that $$\mathbb{P}(X \ge k) = \frac{{{n}\choose{k}} (n-k)!}{n!}$$ ?
• $n!$ is the total number of combinations. Now assume that at least $k$ balls are in the right box, this means in particular, $k$ balls are in the right box, and that's where the factor $\binom{n}{k}$ came from. Now for the rest of the $(n-k)$ balls, they are permuted in any order (in the rest of the $(n-k)$ boxes), and this gives the factor $(n-k)!$. This was the initial thought. Nov 1, 2022 at 9:07