参考

实数列上的运算变换定理.csdn

容斥定理的非数学归纳证明.csdn

错排问题（Derangement）

问题描述

给定 $n$ 个元素，将它们重新排列，使得没有任何一个元素出现在原来的位置上。这样的排列称为“错排”，其数量记作 $!n$。

目标

$$D(n)=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}$$

方法1: 用容斥定理证明

---

一、集合建模

设：
S = { 所有  n  元排列 } S = \{\text{所有 } n \text{ 元排列}\} S={所有 n 元排列}

则：
$|S|=n!$

---

二、定义“坏事件”（固定点）

对每个 $i=1,2,\dots ,n$，定义事件：

A i = { σ ∈ S ∣ σ ( i ) = i } A_i = \{\sigma \in S \mid \sigma(i) = i\} Ai​={σ∈S∣σ(i)=i}

即：第 $i$ 个元素在原位置（固定点）

三、目标（错排定义）

$$D(n)=\left|S-\bigcup _{i=1}^n{A}_i\right|=n!-\left|A_1\cup \cdots \cup A_n\right|\text{\hspace{1em}(1)}$$

$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{k=1}^n(-1{)}^{k-1}\sum _{1\le i_1<\cdots <i_k\le n}\left|A_{i_1}\cap \cdots \cap A_{i_k}\right|\text{\hspace{1em}(2)}$$

$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{i=1}^n(-1{)}^{i-1}{A}_{[i]}\text{\hspace{1em}(3)}$$

四、固定k个的计数

如果固定 $k$ 个位置,剩下 $n-k$ 个任意排列个数为

$\left|A_{i_1}\cap \cdots \cap A_{i_k}\right|=(n-k)!$

所以
$$A_{[i]}=\left(\genfrac{}{}{0ex}{}{n}{k}\right)(n-k)!$$ 带入(1)式便得证。

方法2: 用递推证明

一、递推关系

利用分步乘法原理

先把第一个元素放到一个不是自己位置的地方，一共有 $n-1$ 种选法。
放好之后, 放置第2个元素会出现两种情况：

• 如果没有和对应位置形成互换，那么剩下 $n-1$ 个元素继续错排，对应 $D(n-1)$；
• 如果形成了互换（1 ↔ k），那么这两个位置固定，剩下 $n-2$ 个元素错排，对应 $D(n-2)$
  $$\{\begin{array}{l}D(1)=0,D(2)=1\\ D(n)=(n-1)(D(n-1)+D(n-2)),n\ge 3\end{array}$$

---

二、归一化

令：

$$b_n=\frac{D(n)}{n!}$$

---

三、差分定义

令：

$$c_n=b_n-b_{n-1}$$

---

四、化简递推

由原递推可得：

$$b_n=\left(1-\frac{1}{n}\right)b_{n-1}+\frac{1}{n}{b}_{n-2}$$

移项得：

$$c_n=-\frac{1}{n}{c}_{n-1}$$

---

五、初始结构（直接由归一化得到）

$$b_1=0,b_2=\frac{1}{2}$$

$$c_1=b_1-b_0=-1,c_2=b_2-b_1=\frac{1}{2}$$

（取 $b_0=1$）

---

六、差分展开

$$c_n=\frac{(-1{)}^n}{n!}{c}_0$$

---

七、恢复 $b_n$

$$b_n=\sum _{k=0}^n\frac{(-1{)}^k}{k!}$$

---

八、还原 $D(n)$

$$D(n)=n!b_n$$

---

九、最终结果

$$D(n)=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}$$