递归推导错位排列概率递推公式的错误排查请求

API 探路者

2026-4-21

问题背景

Suppose there are $n$ people invited to a party. Seats are assigned and a name card is made for each guest. However, floral arrangements on the table unexpectedly obscure the name cards. When the $n$ guests arrive, they seat themselves randomly.
Show that the probability that no one seats at the assigned seats is $$P_n = \frac{n-1}{n} P_{n-1} + \frac1n P_{n-2}.$$

我的推导尝试

We consider a letter $i$, where $i \in {1, \dots, n}$.

Let $E$ denote the event that no one sits at the right spot.

Let $X_i$ be an indicator variable s.t. $X_i = 1$ indicates the ith person sits at the right spot.

Then $Pr(E) = Pr(E \cap X_i = 0) + Pr(E \cap X_i = 1)$.

Note that $Pr(E \cap X_i = 1) = 0$ because it's impossible.

Then only need to compute:
$$
\begin{align}
Pr(E \cap X_i = 0)
&= \sum_{j = 1, j \neq i}^{n}Pr(E \cap \text{person i in seat j}) \
&= \sum_{j = 1, j \neq i}^{n}
\left( Pr(E \vert S_{i,j} \cap S_{j,i}) \times Pr(S_{i,j}\cap S_{j,i}) \

Pr(E \vert S_{i,j} \cap S_{j,i}^C) \times Pr(S_{i,j}\cap S_{j,i}^C)
\right)
\end{align}
$$
where $S_{i,j}={\text{person }i\text{ in seat }j}$ and $S_{i,j}^C$ denotes the complement, $S_{i,j}^C={\text{person }i\text{ not in seat }j}$.

Then
$$Pr(E \vert \text{person i in seat j} \cap \text{person j in seat i}) = P_{n-2},$$
$$Pr(E \vert \text{person i in seat j} \cap \text{person j not in seat i}) = P_{n-1},$$
$$Pr(\text{person i in seat j} \cap \text{person j in seat i}) = \frac{1}{n(n-1)},$$
$$Pr(\text{person i in seat j} \cap \text{person j not in seat i}) = \frac{n-2}{n(n-1)}.$$

And this sums up as $$\frac1n P_{n-2} + \frac{n-2}{n}P_{n-1}.$$