第1章：错排问题（又名伯努利装错信封问题）

问题描述

数学家伯努利很粗心。一次，他给朋友寄信时，信和信封全装错了（怀疑他是故意的，正常人都不会这样），请问有多少种装法？

另一种描述：对于一个长度为 $n$ 全排列 $A$，求问有多少种 $A$ 的排列，使得对于所有的整数 $i$，$1 \leq i \leq n$，都有 $A_i \not = i$？

公式推导

第一种：直接推公式，适用于单词询问（这个代码上有点难）

以下内容定义 $A_1,A_2,…,A_n$ 为 $n$ 个集合，$S$ 为全集。

首先，我们要知道容斥原理的公式：

$$\mid A_1 \cup A_2 \cup … \cup A_n \mid = \quad\displaystyle\sum_{i=1}^n \mid A_i \mid - \quad\displaystyle\sum_{1 \leq i < j \leq n} \mid A_i \cap A_j \mid + \quad\displaystyle\sum_{1 \leq i<j<k \leq n} \mid A_i \cap A_j \cap A_k \mid -…+(-1)^{n-1} \mid A_1 \cap A_2 \cap … \cap A_n \mid$$

还有一个定理叫做德·摩根定理：

$$\complement_S (A_1 \cup A_2 \cup … \cup A_n)=\complement_SA_1 \cap \complement_SA_2 \cap … \cap \complement_SA_n$$

当然也可以根据上述两个公式得出：

$$\mid \complement_SA_1 \cap \complement_SA_2 \cap … \cap \complement_SA_n \mid =\mid S \mid -\quad\displaystyle\sum_{i=1}^n \mid A_i \mid + \quad\displaystyle\sum_{1 \leq i < j \leq n} \mid A_i \cap A_j \mid - \quad\displaystyle\sum_{1 \leq i<j<k \leq n} \mid A_i \cap A_j \cap A_k \mid +…+(-1)^n \mid A_1 \cap A_2 \cap … \cap A_n \mid$$

那么接下来进入正题

对于一个数列所有排列的总集合 $S$，显然有 $\mid S \mid =n!$。建立 $n$ 个集合 $A_1,A_2,…,A_n$，其中 $A_i(1 \leq i \leq n)$ 代表第 $i$ 个数归位（或者说第 $i$ 个信封寄对了）所有方法的总集合，显然有 $\mid A_i \mid =(n-1)!$。

而我们要求的，就是下面这一串：（因为 $A_i$ 代表第 $i$ 个归位的总数，$\complement_SA_i$ 就代表 $i$ 不归位的总数，他们的交集就是全部不归位的总数）

$$\mid \complement_SA_1 \cap \complement_SA_2 \cap … \cap \complement_SA_n \mid$$

它等于：

$$\mid S \mid -\quad\displaystyle\sum_{i=1}^n \mid A_i \mid + \quad\displaystyle\sum_{1 \leq i < j \leq n} \mid A_i \cap A_j \mid - \quad\displaystyle\sum_{1 \leq i<j<k \leq n} \mid A_i \cap A_j \cap A_k \mid +…+(-1)^n \mid A_1 \cap A_2 \cap … \cap A_n \mid$$

由于我们知道 $\mid S \mid =n!$，$\mid A_i \mid =(n-1)!$，同样可以推出 $\mid A_i \cap A_j \mid =(n-2)!$，$\mid A_i \cap A_j \cap A_k \mid =(n-3)!$……

上面那一串就等于：

$$n!-C_n^1(n-1)!+C_n^2(n-2)!-C_n^3(n-3)!+…+(-1)^nC_n^n0!$$

也就是：

$$n!-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+…+(-1)^n\frac{n!}{n!}$$

提取一下，就得到了最终公式：

$$n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+…+(-1)^n\frac{1}{n!})$$

顺带一提，我差点把自己绕晕了，还是第二种方法好理解一些。

第二种：递推，一般适用于多次询问（这个代码就简单多了）

我们设错排问题的函数为 $f$。

已知 $f_1=0$，$f_2=1$。对于每一个 $f_i(i \geq 3)$，都能根据如下分析进行递推：

• 首先，第 $i$ 个数是基于之前的错排添加的，则 $i$ 必然在原位。
• 数列中最多只能有 $2$ 个归位的数，因为当有大于 $2$ 个归位的数时，则无法通过一次交换两个数得到错排序列。
• 当序列中仅有 $i$ 一个数在原位时，则剩余的数构成 $i-1$ 个数的错排。此时将 $i$ 与前面 $i-1$ 个数任意一个交换即可得到错排序列，方案数为 $f_{i-1}(i-1)$
• 当序列中有两个数在原位时，则除了 $i$ 外，前 $i-1$ 个数都可能成为第二个归位的数，设这个数为 $j$。剩下的数形成 $i-2$ 个数的错排。但是，要想形成错排序列，则必须交换 $i$ 和 $j$，因此方案数为 $f_{i-2}(i-1)$。

综上所述，我们得到了递推公式 $f_i=(f_{i-1}+f_{i-2})(i-1)$。

第二种方法雀食更简单……

以上便是错排问题的公式分析。我写这个写了一天，不介意给个赞吧？