有 $n$ 个座位和对应的 $n$ 个人（编号从$0…(n - 1)$）。0号人随机选择一个座位，然后剩下的人 $i$ 依次按如下原则选择座位：
若 $i$ 对应的座位还空着，则选 $i$ 号座位
否则随机从余下的座位中选一个
求：
每个人坐在自己对应座位的概率 $P(i), i = 0, 1, … , (n - 1)$
$P(0) = \frac{1}{n}, P(1) = \frac{n - 1}{n}$
$0$ 号人的行为与其它人不同，其选择座位时，虽然 $0$ 号座位空着，其也会随机选择座位，所以 $P(0)$ 是单独的。
考虑 $i$ 就位的概率，
若 $0$ 选了 $0$ 位置，则所有元素就位，此情况概率为 $\frac{1}{n}$
若 $0$ 选了 $[i + 1， n - 1]$ 之间的位置，$i$ 也一定就位，此情况总概率为 $\frac{n - i - 1}{n}$
若 $0$ 选了 $i$ ，$i$ 一定不能就位
若 $0$ 选了 $[1, i)$ 之间的某位置 $k$，则 $[1, k - 1]$ 一定都会就位，等到 $k$ 时，其位置已被占领，$k$ 会随机选一个，其和最开始的第 $0$ 号人行为一样，不妨改认为 $k$ 的正确座位为 $0$ 号座位，$f(n, i)$ 变成子问题 $f (n - k，i - k)$，其中 $f$ 的第一个参数为新向量长度，第二个参数为 $i$ 的新顺序编号
综上有，
$f(n, i) = \frac{1}{n} + \frac{n - i - 1}{n} + \frac{1}{n} * \sum \limits_{1}^{i - 1} {f(n - k, i - k)}$
归纳，假设对前面的 $n, i$ 取值，有 $f(n, i) = \frac{n - i}{n - i + 1}$，现求 $f(n, i)$
由归纳假设，$f(n - k, i - k) = \frac{n - i}{n - i + 1}$ （与 $k$ 无关！）
则 $f(n, i) = \frac{n - i}{n} + \frac{1}{n} * (i - 1) * \frac{n - i}{n - i + 1}$
$= \frac{(n - i)(n - i + 1)}{n(n - i + 1)} + \frac{(n - i)(i - 1)}{n(n - i + 1)}$
$= \frac{(n - i)n}{n(n - i + 1)}$
$= \frac{n - i}{n - i + 1}$
于是有：$f(n, i) = \frac{n - i}{n - i + 1} (n \ge 1)$
来自 826-纯学习讨论群
首先观察到这样一个特点，第 $i$ 号人将要选座位时，$[1, i - 1]$ 的座位一定是被占据的。（可以反证证明）
考虑第 $i$ 号人面对的座位已选情况（只看座位占据情况，抹去具体编号）。
我们考虑还有一个被占据的位置在哪里，其一定为 $0 ∪ [i, n - 1]$ 之一。那么，其等概率分布在这 $n - i + 1$ 个位置之一吗？
无法确定，尤其 $0$ 位置看起来还比较特殊。但是可以知道的是：其如果分布在 $[i, n - 1]$ 的话，一定是等概率分布的，因为对于前面的人，$[i, n - 1]$ 的所有座位都是没有任何差别的。
设 $P_1(i)$为：第 $i$ 号人将要选座位时，座位占据情况为 $[0, i - 1]$ 的概率。
设 $P_2(i)$为：第 $i$ 号人将要选座位时，座位占据情况为 $[1, i - 1] ∪ [i, n - 1]之一$ 的概率。
$P_1(i) + P_2(i) = 1$ 且对于 $P_2$ 发生的情况，在 $[i, n - 1]$ 是等概率分布的
若 $i$ 号人要坐在自己的位置上，当且仅当 $i$ 号座位是空着的，所以，还有一个被占据的位置要为 $0 ∪ [i + 1, n - 1]$ 之一。
$P(i) = P_1(i) + P_2(i) * (1 - \frac{1}{n - i})$
好消息是，$P_1(i)$ 可以直接归纳求出来！为 $\frac{1}{n - i + 1}$
证明：
第 $i$ 号人选完座位后（第 $i + 1$ 号人将要选座位时，$P_1(i + 1)$），要仍然保持为前缀占据(已选位置为$[0, i]$)，则 要么第 $i$ 号人将要选择时座位情况就是前缀占据；要么其时第 $i$ 号座位已被占据，按题目条件，其随机选取，以 $\frac{1}{n - i}$ 的概率选中 $0$ 号座位。
即 $P_1(i + 1) = P_1(i) + P_2(i) * \frac{1}{n - i} * \frac{1}{n - i}$
（第一个 $* \frac{1}{n - i}$ 是 $P_2$ 发生的情况还有一个被占据的位置在 $i$ 的概率，第二个 $* \frac{1}{n - i}$ 是 $i$ 发现自己座位被占据，按题意随机选择 ${0} ∪ [i + 1, n - 1]$ 之一，选中 $0$ 的概率）
$P_1(1) = \frac{1}{n}$
假设 $P_1(i) = \frac{1}{n - i + 1}$，归纳可得，$P_1(i + 1) = \frac{1}{n - i}$
于是，$P(i) = \frac{n - i}{n - i + 1} (i \ge 1)$
仅从结果来看，当 $i$ 将要选座位时，还有一个被占据的位置是等概率分布在 ${0} ∪ [i, n - 1]$ 这 $n - i + 1$ 个座位之一的，$i$ 能坐上自己位置的概率为 $\frac{n - i}{n - i + 1}$ 。
$P(0) = \frac{1}{n}$
$P(i) = \frac{n - i}{n - i + 1} (1 \le i \le n - 1)$