本节对应原书 PDF 第 225–230 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

9.2.1 对称筛公式

当集合的性质在计数中具有对称性时容斥原理有着另一种表示，它的表达更为简洁.设 S,A_i 的含义如定理 9.1 所述，其中 i=1,\cdots,m.令

|S|=N,\quad N_k=|A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}|

其中，1 \leqslant i_1<i_2<\cdots<i_k \leqslant m，k=1,2,\cdots,m，则容斥原理变成

N_0=N-\binom{m}{1}N_1+\binom{m}{2}N_2-\cdots+(-1)^m\binom{m}{m}N_m=N+\sum_{t=1}^{m}(-1)^t\binom{m}{t}N_t

这个公式称为对称筛公式.

对称筛公式是容斥原理的特殊表示，只有性质在计数中具有对称性时才能使用.这种对称性的表现是：在 m 种性质中，具有其中任何 1 条性质的元素数都等于 N_1，具有其中任何 2 条性质的元素数都等于 N_2，\cdots\cdots，具有其中任何 m-1 条性质的元素数都等于 N_{m-1}.

解读：原式里每个交集的大小各不相同，写起来是一堆 |A_i \cap A_j|；一旦任何 k 条性质的交集大小都相同，就能把它们统一记成 N_k，系数自然变成「从 m 条里选 k 条」的组合数 \binom{m}{k}。

下面考虑错位排列的计数问题.这个问题起源于一个著名的帽子寄存问题.有 n 个人在参加晚会时寄存了自己的帽子.可是保管人忘记放寄存号，当每个人领取帽子时，他只能随机选择一顶帽子交给寄存人.问在 n! 种领取帽子的方式中有多少种方式使得每个人都没有领到自己的帽子？如果将这些人 与他们的帽子分别标号为 1,2,\cdots,n.设 j 领到的帽子标号为 i_j，j=1,2,\cdots,n，那么这些人领到的帽子可以用排列 i_1i_2\cdots i_n 来表示，其中每个人都没有领到自己帽子的排列 i_1i_2\cdots i_n 满足 i_j \neq j，j=1,2,\cdots,n.这种排列称为错位排列.错位排列数记作 D_n，可以证明 D_n=n!\left[1-\frac{1}{1!}+\frac{1}{2!}-\cdots+(-1)^n\frac{1}{n!}\right].

设 S 为 \{1,2,\cdots,n\} 的排列的集合，P_i 是其中 i 处在排列中的第 i 位的性质，i=1,2,\cdots,n.错位排列数 D_n 就是 S 中不具有以上任何一条性质的排列数.显然这些性质具有对称的特点，根据对称筛公式得到

N=n!
N_1=(n-1)!
N_2=(n-2)!
\vdots
N_k=(n-k)!
\vdots
N_n=0!
\begin{aligned} D_n &= n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!-\cdots+(-1)^n\binom{n}{n}0!\\ &= n!\left[1-\frac{1}{1!}+\frac{1}{2!}-\cdots+(-1)^n\frac{1}{n!}\right] \end{aligned}

可以证明错位排列数具有下面的性质.

（1）错位排列数满足下面的方程：

\begin{cases} D_n=(n-1)(D_{n-2}+D_{n-1})\\ D_1=0,D_2=1 \end{cases}

证明 按照第一位的数是 2,\cdots,n 将错位排列进行分类，有 n-1 类.根据对称性，这 n-1 类中的排列个数相等.考虑第一位为 2 的类，将这个类按照第二位是 1 或不是 1 进一步划分成两个子类.如果第二位是 1，那么后面的 n-2 个数构成 \{3,4,\cdots,n\} 的错位排列，有 D_{n-2} 种构成方法；如果第二位不是 1，那么从这位起的 n-1 位构成 \{1,3,\cdots,n\} 的错位排列，有 D_{n-1} 种构成的方法.因此 D_{n-2}+D_{n-1} 是第一位为 2 的错位排列个数，再乘以 n-1 就表示了所有的错位排列数.

如果将所有的错位排列数列出来，可以得到数列 D_1,\cdots,D_n,\cdots，上述方程将这个数列的第 n 项 D_n 与前面的 n-1 项及 n-2 项联系起来.这种方程称为递推方程.如果知道了 D_2 与 D_1，反复使用这个方程，就可以求出任何一个错位排列数.求解这个递推方程也可以得到关于 D_n 的公式，与容斥原理得到的结果一样.关于递推方程的求解方法和在计数问题中的应用将在下一章讨论.

（2）错位排列数 D_n 满足下面恒等式（这里规定 D_0=1）：

n!=\binom{n}{0}D_n+\binom{n}{1}D_{n-1}+\binom{n}{2}D_{n-2}+\cdots+\binom{n}{n}D_0

证明 等式左边是 S=\{1,2,\cdots,n\} 的所有排列的总数.将这些排列按照 n 个数中有多少个数不在其自然位置上进行分类，这里数 i 的自然位置是指排列中的第 i 位.考虑恰好有 n-i 个数不在其自然位置的排列个数.首先从 \{1,2,\cdots,n\} 中选出 i 个数，有 \binom{n}{i} 种选法.将这些数放在它们的自然位置上，然后对剩下的 n-i 个数进行错位排列，排列的方法有 D_{n-i} 种，因此 \binom{n}{i}D_{n-i} 计数了恰好有 n-i 个数不在其自然位置的排列.使用加法法则，等式右边也计数了 S 的所有的排列.

（3）错位排列数满足如下性质：D_n 为偶数当且仅当 n 为奇数.

这条性质的证明留作练习.

（4）当 n 充分大时，错位排列数与排列总数的比值趋向于 1/\mathrm{e}.

证明 错位排列的个数满足公式

D_n=n!\left[1-\frac{1}{1!}+\frac{1}{2!}-\cdots+(-1)^n\frac{1}{n!}\right]

排列总数是 n!，因此

\frac{D_n}{n!}=1-\frac{1}{1!}+\frac{1}{2!}-\cdots+(-1)^n\frac{1}{n!}

考察 \mathrm{e}^{-1} 的展开式，可以得到

\mathrm{e}^{-1}=1-\frac{1}{1!}+\frac{1}{2!}-\cdots+\cdots
\mathrm{e}^{-1}=\frac{D_n}{n!}+(-1)^{n+1}\frac{1}{(n+1)!}+(-1)^{n+2}\frac{1}{(n+2)!}+\cdots
\lim_{n \to \infty}\frac{D_n}{n!}=\mathrm{e}^{-1}

上述比值反映了出现错位排列的概率，关于离散概率的概念及其性质将在后面第 12 章加以介绍.

解读：D_n/n! 是 \mathrm{e}^{-1} 的部分和，余项由 \pm\frac{1}{(n+1)!} 起步，随 n 增大迅速趋于 0，所以极限就是 \mathrm{e}^{-1} \approx 0.368。这解释了为什么「所有人都拿错帽子」的概率几乎与人数无关。

例 9.6 在 8 个字母 A,B,C,D,E,F,G,H 的全排列中，求使得 4 个字母不在原来位置的排列数.

解 从这 8 个字母中选出 4 个字母的方法数是 \binom{8}{4}=\frac{8!}{4!4!}=70，这 4 个字母的错位排列数为

D_4=4!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}\right)=24\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right)=12-4+1=9

因此所求的排列数是 N=70 \times 9=630.

解读：题目只要求「4 个字母不在原位」，没说哪 4 个，所以先选人再错排，两步相乘。剩下 4 个字母可以任意就位，这正是一开始乘上 \binom{8}{4} 而不是 \binom{8}{4} \cdot 4! 的原因。

9.2.2 棋盘多项式与有限制条件的排列

本节主要讨论有限制条件下排列的计数问题，这里的限制指的是对元素排列位置的限制，例如不允许 1 排在第 5 位，不允许 2 排在第 3 位\cdots\cdots不难看出，错位排列也是一种有限制条件的排列.它们的区别是，这里的限制更加一般化，不像错位排列对每个数的限制都一样.为了解决这种排列的计数，先引入第三个组合计数模型——棋盘布棋问题.

棋盘布棋问题（组合计数模型 3）.一个棋盘由大小相同的正方形方格构成，一个方格中允许放入一个棋子.在向棋盘布棋时，要求任何两个棋子既不能布在棋盘的同一行，也不能布在同一列上.

n 个元素的排列与 n 个棋子在 n \times n 棋盘的布棋方案是一一对应的.排列 i_1i_2\cdots i_n 表示第一行的棋子放在第 i_1 列，第二行的棋子放在第 i_2 列，\cdots\cdots，第 n 行的棋子放在第 i_n 列.例如图 9.2 的布棋方案对应于 \{1,2,\cdots,6\} 的排列 251364.

原书图9.2

如果不允许元素 i 出现在排列的第 j 位上，相当于棋盘的第 i 行第 j 列的方格不能布棋，这种不允许布棋的方格称为禁区.这样一来，带限制条件的排列问题就与带禁区棋盘的布棋问题之间建立了一一对应.下面通过对棋盘布棋方案的计数来解决带限制条件排列的计数问题.

设 C 是给定棋盘，r_k(C) 表示 k 个棋子在棋盘 C 上的布棋方案数.规定 r_0(C)=1.还可以证明 r_k(C) 满足下面的递推性质.

（1）在 C 中任意选定一个方格，令 C_i 表示在 C 中去掉选定方格所在的行和列之后剩余的棋盘，\bar{C}_i 表示在 C 中去掉指定方格后剩余的棋盘，那么有

r_k(C)=r_{k-1}(C_i)+r_k(\bar{C}_i)

证明 按照在指定方格中放棋子或者不放棋子将布棋方案分成两类：如果指定方格有棋子，那么剩下的 k-1 个棋子只能布到剩下的 k-1 行 k-1 列的棋盘中去，布棋方案数是 r_{k-1}(C_i)；如果指定方格没有棋子，那么这 k 个棋子将布到除去这个方格外的剩余棋盘 \bar{C}_i 上，方案数是 r_k(\bar{C}_i).根据加法法则公式得证.

（2）设 C 由 C_1,C_2 两个分离的棋盘构成，这里“分离”的含义是指 C_1 与 C_2 不存在共同的行和列.换句话说，它们的布棋方案相互独立.那么有

r_k(C)=\sum_{i=0}^{k}r_i(C_1)r_{k-i}(C_2)

证明 将在 C 上的布棋方案按照在 C_1 中的棋子数 i 进行分类，其中 i=0,1,\cdots,k.考虑其中的任何一类.假设在 C_1 中的棋子数为 i，那么剩下的 k-i 个棋子将布到 C_2.由于 C_1 与 C_2 的布棋是独立的，因此 r_i(C_1)r_{k-i}(C_2) 就是 C_1 中恰有 i 个棋子的布棋方案数.根据加法法则，等式得证.

这两个方程是关于布棋方案数的递推方程，可以根据这个方程与初值计算给定棋盘的布棋方案数.也可以使用另一种方法，那就是利用棋盘多项式来求所有的布棋方案数.下面先给出棋盘多项式的概念.

定义 9.1 设 C 为给定棋盘，在 C 上的布棋方案数构成数列 r_0(C),r_1(C),r_2(C),\cdots,r_k(C),\cdots.用这个数列的项 r_k(C) 作为 x^k 的系数，构成形式幂级数

r_0(C)+r_1(C)x+r_2(C)x^2+\cdots+r_k(C)x^k+\cdots

称为 C 的棋盘多项式，记作 R(C)，即

R(C)=\sum_{k=0}^{\infty}r_k(C)x^k

根据上面关于布棋方案数的递推方程，不难得到有关棋盘多项式的递推式：

R(C)=xR(C_i)+R(\bar{C}_i)
R(C)=R(C_1)R(C_2)

这里的 C_i,\bar{C}_i,C_1,C_2 的含义与前面相同.

利用这两个公式和一些简单棋盘的多项式，可以计算一些比较复杂的棋盘多项式.下面给出一些简单棋盘多项式的有关结果和计算实例.

待核：原书以下 4 个棋盘多项式等式的左端为手绘小棋盘图形，扫描件中为图形而非文字，无法逐字照抄；此处保留右侧算式与数值，图形位置用文字代称。

R(\text{一格棋盘})=1+x
R(\text{横排两格棋盘})=R(\text{竖排两格棋盘})=1+2x
R(\text{两格不同行不同列的棋盘})=1+2x+x^2
\begin{aligned} R(\text{三格棋盘}) &= xR(\text{竖排两格棋盘})+R(\text{田字棋盘})\\ &= x(1+2x)+x(1+x)+R(\text{两格不同行不同列的棋盘})\\ &= 2x+3x^2+1+3x+x^2=1+5x+4x^2 \end{aligned}

在计算中可以使用对称的性质，如果一个棋盘 C 经过旋转或者翻转变换到另一个棋盘 C'，那么 C 与 C' 的棋盘多项式相等.

解读：R(C)=xR(C_i)+R(\bar{C}_i) 就是「在选定格放子 / 不放子」两种情形的分流：放子则乘 x 并删掉整行整列，不放子则只删掉这一格。把它反复用在形状复杂的棋盘上，就能拆成几个已知的简单棋盘。

下面考虑有限制条件的排列问题.

定理 9.2 设 C 是 n \times n 的具有给定禁区的棋盘，这个禁区对应于 \{1,2,\cdots,n\} 中的元素在排列中不允许出现的位置，则这种有限制条件的排列数为

n!-r_1(n-1)!+r_2(n-2)!-\cdots+(-1)^nr_n

其中 r_i 是 i 个棋子布置到禁区的方案数.

证明 先不考虑禁区的限制，不带标号的棋子布到 n \times n 棋盘的方案数为 n!，为了定义排列的性质，考虑将棋子进行标号，那么带标号棋子的布棋方案数为 n!n!.这两种方案数恰好相差 n! 倍.

令 P_j 表示第 j 个棋子落入禁区的性质，j=1,2,\cdots,n.任意给定 k \in \{1,2,\cdots,n\}，考虑 k 个选定的被标号棋子落入禁区的放棋方案数.k 个不带标号的棋子落入禁区的方案有 r_k 种，对每一种方案，棋子被标号的方法有 k! 种，因此 k 个选定的被标号棋子落入禁区的放棋方案数是 r_kk!.剩下的 n-k 个被标号的棋子可以任意分布在剩下的 (n-k) 行 (n-k) 列的棋盘上，有 (n-k)!(n-k)! 种方法.因此，N_k=k!\ r_k(n-k)!(n-k)!.

令 N_0 和 N 分别表示带标号与不带标号棋子的有禁区的布棋方案数，使用对称筛公式可以得到

\begin{aligned} N_0 &= n!n!-\binom{n}{1}r_1(n-1)!(n-1)!+\binom{n}{2}2!r_2(n-2)!(n-2)!\\ &\quad -\cdots+(-1)^k\binom{n}{k}k!r_k(n-k)!(n-k)!+\cdots+(-1)^n\binom{n}{n}n!r_n\\ &= n!n!-r_1n!(n-1)!+r_2n!(n-2)!-\cdots+(-1)^kr_kn!(n-k)!\\ &\quad +\cdots+(-1)^nr_nn! \end{aligned}
N=n!-r_1(n-1)!+r_2(n-2)!-\cdots+(-1)^kr_k(n-k)!+\cdots+(-1)^nr_n

为了使用这个定理，首先需要针对禁区来计算棋盘多项式，并找到公式中出现的所有 r_1,r_2,\cdots,r_n.如果禁区面积很大，而允许布棋的部分棋盘反而较小，那么针对允许布棋的部分棋盘来计算棋盘多项式，从而直接求出布棋方案数反而更简单.这就说明定理 9.2 仅对小禁区的情况有效.此外，如果原始棋盘不是 n \times n 的棋盘，那么定理 9.2 也不适用.比如说对于一个分配工作的实际问题，需要分配工作的有 3 个人，工作有 6 种，确定了一个 3 \times 6 的棋盘.每个人的条件决定了所不能从事的工作种类，这些构成了棋盘的禁区.求有多少种可能的分配方案.这个问题就不能使用定理 9.2 求解.一种可行的解决办法就是直接使用棋盘多项式确定分配方案数.

解读：证明先给棋子标号，是为了让「落入禁区」这件事能写成 n 条明确的、彼此对称的性质，从而套用对称筛公式；最后把 n! 这个倍数约掉，才得到只含 r_i 的排列数公式。

例 9.7 G,L,W,Y 是 4 位工作人员，A,B,C,D 为 4 项工作.每个人不能从事的工作任务情况列举如下：G 不能从事工作 B，L 不能从事工作 B 和 C，W 不能从事工作 C 和 D，Y 不能从事工作 D.求可能的分配方案数 N.

图 9.3 的阴影区域对应了分配方案的禁区，这个禁区的棋盘多项式是

1+6x+10x^2+4x^3

原书图9.3

使用定理 9.2 得到

N=4!-6 \cdot 3!+10 \cdot 2!-4 \cdot 1!=24-36+20-4=4

解读：1+6x+10x^2+4x^3 的系数依次就是禁区上放 0、1、2、3 个互不同行同列的棋子的方案数，直接代入定理 9.2 的公式即可，不需要再单独处理「至少一个冲突」的组合逻辑。

下面使用定理 9.2 计算错位排列数.

例 9.8 计算 D_n.

设错位排列对应的棋盘禁区为 C，C 恰好由左上到右下的 n 个连续的方格构成.这些方格是彼此分离的，因此有

\begin{aligned} R(C) &= R(\text{由 } n \text{ 个彼此分离的单格组成的棋盘})=(1+x)^n\\ &= 1+C(n,1)x+C(n,2)x^2+\cdots+C(n,n)x^n \end{aligned}

因此 r_i=C(n,i)，代入定理 9.2 的公式，得

\begin{aligned} D_n &= n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!-\cdots+(-1)^n\binom{n}{n}0!\\ &= n!-n!+\frac{1}{2!}n!-\frac{1}{3!}n!+\cdots+(-1)^n\frac{1}{n!}n!\\ &= n!\left[1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}\right] \end{aligned}

这与前面的结果完全一样.

解读：错位排列的禁区正好是主对角线，n 个单格互不同行也不同列，所以棋盘多项式直接就是 (1+x)^n——这正是定理 9.2 与对称筛公式给出同一结果的原因。