随机排列的不动点

题

\(n\) 个人把帽子扔进一堆，再每人随机拿回一顶（即 \(1, \ldots, n\) 的均匀随机排列）。拿回自己帽子的人数 \(X\) 期望是多少？方差呢？没有一个人拿对的概率是多少？

一句话

\(E[X] = 1\)，\(\mathrm{Var}(X) = 1\)，不管 \(n\) 是 3 还是一百万；没人拿对的概率趋于 \(1/e \approx 0.368\)，而且收敛快得离谱——\(n = 10\) 时误差已经只有 \(2 \times 10^{-8}\)。

关键技巧

拆成指示变量，别碰分布。 令 \(I_i = [\sigma(i) = i]\)，则 \(X = \sum_i I_i\)。每个人拿对的概率是 \(1/n\)，期望线性性不要求独立：

\[ E[X] = \sum_{i=1}^n P(\sigma(i) = i) = n \cdot \frac1n = 1 \]

方差要二阶矩，还是指示变量。\(X(X-1)\) 数的是有序对 \((i, j)\)、\(i \ne j\)、两人都拿对：

\[ E[X(X-1)] = n(n-1) \cdot P(\sigma(i) = i, \sigma(j) = j) = n(n-1) \cdot \frac{1}{n(n-1)} = 1 \]

于是 \(E[X^2] = 2\)，\(\mathrm{Var}(X) = 2 - 1^2 = 1\)（\(n \ge 2\)）。

同样的计算推到 \(m\) 阶：\(E\bigl[X(X-1)\cdots(X-m+1)\bigr] = 1\) 对所有 \(m \le n\) 成立——这正是 Poisson(1) 的阶乘矩。前 \(n\) 阶矩和 Poisson(1) 完全一致，分布收敛到 Poisson(1) 是顺理成章的事。

解

期望与方差如上，都是 1。

恰有 \(k\) 人拿对：先选这 \(k\) 人，其余 \(n-k\) 人全部错排。容斥给出错排数 \(D_m = m!\sum_{j=0}^m \frac{(-1)^j}{j!}\)，于是

\[ P(X = k) = \frac{1}{k!} \sum_{j=0}^{n-k} \frac{(-1)^j}{j!} \;\xrightarrow{n \to \infty}\; \frac{e^{-1}}{k!} \]

没人拿对：\(P(X=0) = \sum_{j=0}^n \frac{(-1)^j}{j!}\)，是 \(e^{-1}\) 泰勒级数的部分和，误差不超过 \(\frac{1}{(n+1)!}\)。\(n=4\) 时 \(3/8 = 0.375\)，\(n=10\) 时 \(16481/44800 = 0.3678794\ldots\)，与 \(1/e = 0.3678794\ldots\) 到小数点后 7 位都一样。

延伸

期望圈数是 \(H_n\)：排列拆成若干个圈，不动点就是长度 1 的圈。元素 \(i\) 所在圈的长度 \(L_i\) 在 \(1, \ldots, n\) 上均匀分布，圈数 \(= \sum_i \frac{1}{L_i}\)（每个长 \(\ell\) 的圈被它的 \(\ell\) 个成员各记 \(\frac1\ell\)），所以 \(E[\text{圈数}] = n \cdot \frac1n \sum_{\ell=1}^n \frac1\ell = H_n\)。同一个调和级数在集卡问题里也出现；面条打结成圈是它的"奇数版"\(\sum \frac{1}{2k-1}\)。
长 \(\ell\) 的圈期望个数恰好是 \(1/\ell\)（\(\ell \le n\)），\(\ell = 1\) 就回到 \(E[X] = 1\)。
没人拿对与恰一人拿对几乎等概率：\(P(X = 0)\) 与 \(P(X = 1)\) 在 \(n\) 有限时只差 \(\frac{(-1)^n}{n!}\)，\(n = 10\) 时两者都是 \(0.36788\)，肉眼无法分辨。
常见错误：以为"人越多越容易有人拿对"或"越难有人拿对"。两种直觉都错——\(n\) 变大时每人命中率 \(1/n\) 变小，但人数 \(n\) 变多，两者恰好抵消。
同款技巧：随机图的三角形个数、字符串中某模式的出现次数、生日问题里的同日对数，都是"指示变量求和 + 线性性"一步出期望，再用二阶阶乘矩算方差。

数值验证

小 \(n\) 全排列枚举得精确矩与圈数，公式核对 Poisson 极限，\(n = 52\)（一副牌）蒙特卡洛：

from fractions import Fraction as F
import itertools, math, random

def stats(n):
    """枚举全部 n! 个排列：不动点分布、各阶矩、平均圈数。"""
    cnt, cyc = [0] * (n + 1), 0
    for p in itertools.permutations(range(n)):
        cnt[sum(p[i] == i for i in range(n))] += 1
        seen = [False] * n
        for i in range(n):
            if not seen[i]:
                cyc += 1
                while not seen[i]: seen[i] = True; i = p[i]
    N = math.factorial(n)
    d = [F(c, N) for c in cnt]
    mom = [int(sum(k ** m * d[k] for k in range(n + 1))) for m in (1, 2, 3, 4)]  # 恰为整数
    return d, mom, F(cyc, N)

for n in (3, 4, 8):
    d, mom, cyc = stats(n)
    print(n, mom, mom[1] - mom[0] ** 2, cyc)
# 3 [1, 2, 5, 14] 1 11/6
# 4 [1, 2, 5, 15] 1 25/12
# 8 [1, 2, 5, 15] 1 761/280

def p_k(n, k):
    """恰有 k 个不动点：选 k 个固定，其余错排。"""
    return F(1, math.factorial(k)) * sum(F((-1) ** j, math.factorial(j)) for j in range(n - k + 1))

print(p_k(4, 0), p_k(10, 0), float(p_k(10, 0)) - math.exp(-1))
# 3/8 16481/44800 2.3114271940904985e-08
print([round(float(p_k(10, k)), 5) for k in range(5)])
print([round(math.exp(-1) / math.factorial(k), 5) for k in range(5)])
# [0.36788, 0.36788, 0.18394, 0.06131, 0.01534]
# [0.36788, 0.36788, 0.18394, 0.06131, 0.01533]

random.seed(1)
T, n, tot, zero = 200000, 52, 0, 0
for _ in range(T):
    p = list(range(n)); random.shuffle(p)
    f = sum(p[i] == i for i in range(n)); tot += f; zero += f == 0
print(tot / T, zero / T)                      # 0.99857 0.36842