有限制的放球入罐概率问题

力工

设$n\geqslant 2$.今有$n$个罐子和$n$个球，球和罐子皆以$1$至$n$编号，现欲按号码递增顺序依次将球放入罐子，规则如下：$1$号球不得入$1$号罐子，但可随意放入其它各罐，对于$k\geqslant2$,中要$k$号罐空着，就把$k$号球放入$k$号罐 ，否则就随意放入一个空罐，如此下去，显然$n$号球就只有一种放法.试求$n$号球恰好放入$n$号的罐的概率。

kuing

先修改一下规则：去掉“`1` 号球不得入 `1` 号罐”的限制，即 `1` 号球随机放入 `1` 至 `n` 号罐中的任意一个。

修改规则后，记 `P(n)` 为有 `n` 个球和 `n` 个罐，编号都是 `1` 至 `n`，最终 `n` 号球放入 `n` 号罐的概率。

显然 `P(2)=1/2`，当 `n\geqslant3` 时：

（1）若 `1` 号球放入 `1` 号罐，则显然所有球都会按编号放回自家罐，必满足要求，这种情况发生的概率为 `1/n`。

（2）若 `1` 号球放入 `k` 号罐（`k\in[2,n-1]`），那么 `2` 至 `k-1` 号球都得放回自家罐，放完这些之后，尚未放置的球为 `k` 至 `n` 号，空的罐为 `1` 号以及 `k+1` 至 `n` 号。

现在，我们把已经放置好的球和罐都扔掉，然后将尚未放置的球和罐的号码都减去 `k-1`（`1` 号罐除外）。

此时便等价于有 `n-k+1` 个球和 `n-k+1` 个罐的情形，因此此后满足要求的概率为 `P(n-k+1)`。

综合（1）（2），有
\[P(n)=\frac1n+\frac1nP(n-1)+\frac1nP(n-2)+\cdots+\frac1nP(2),\]
于是
\begin{align*}
P(3)&=\frac13+\frac13P(2)=\frac13\left(1+\frac12\right)=\frac12,\\
P(4)&=\frac14+\frac14P(3)+\frac14P(2)=\frac14\left(1+\frac12+\frac12\right)=\frac12,\\
P(5)&=\frac15+\frac15P(4)+\frac15P(3)+\frac15P(2)=\frac15\left(1+\frac12+\frac12+\frac12\right)=\frac12,\\
&\cdots
\end{align*}
如此类推，得到 `P(k)=1/2`（`\forall k\geqslant2`）。

也就是说，修改规则后，无论 `n` 多大，所求概率都是 `1/2`（或许会有更简单的解释！🤔）

最后再由修改规则后的概率计算修改规则前的概率，设修改规则前所求的概率为 `p`，则
\[\frac1n+\left(1-\frac1n\right)p=\frac12,\]
解得
\[p=\frac{n-2}{2(n-1)},\]
这便是原题的结果。