匹配问题

设有 $n$ 个元素，两排列比较的“匹配数”就是固定点个数。

恰有 $r$ 个匹配：先选出这 $r$ 个固定点，再让剩余 $n-r$ 个位置构成一个无固定点排列（错排）。

错排数记为 $D_m$，则

$$\boxed{\mathbb{P}(\text{恰 }r\text{ 个匹配})=\frac{\binom{n}{r}D_{n-r}}{n!}}.$$

其中

$$D_m=m!\sum_{k=0}^m\frac{(-1)^k}{k!}\approx \frac{m!}{e}.$$

当 $n$ 很大且 $r$ 固定时，该分布近似 Poisson(1)：

$$\mathbb{P}(r)\approx \frac{e^{-1}}{r!}.$$

---

英文解析

$$D_m=m!\sum_{k=0}^m\frac{(-1)^k}{k!}\approx \frac{m!}{e}.$$ $$\mathbb{P}(r)\approx \frac{e^{-1}}{r!}.$$