【组合数学】错位排序

错位排序：编号为 \(1\) 到 \(n\) 的球装进编号 \(1\) 到 \(n\) 的盒子里，问每个球与它所在的盒子编号都不同的方案数。

公式：设 \(D_n\) 表示 \(n\) 个球的方案数，则：\(D_n=(n-1)(D_{n-1}+D_{n-2})\) 。

证明：

设 \(D_n\) 前的都已求出，现在装第 \(n\) 个球：

规定 \(n\) 号装进 \(k\) 号盒子 ，再装 \(k\) 号球：

• \(k\) 号球一定装进 \(n\) 号盒子，则剩余 \(n-2\) 个球错位排序，共 \(D_{n-2}\) 种
• \(k\) 号球不能装进 \(n\) 号盒子，则等价于 把 \(n\) 号盒子当成 \(k\) 号盒子 ，这就变成把 \(n-1\) 个球错位排序，共 \(D_{n-1}\) 种

而 \(k\) 的范围是 \(1\) 到 \(n-1\)，所以 \(D_n=(n-1)(D_{n-1}+D_{n-2})\) ，证毕。