返回：0100 离散数学课程总目录 · 上一章：0121 递推方程与生成函数 · 下一章：0123 命题逻辑

1、学习目标

本章处理两类最容易“数重/漏数”的问题：

1
2
限制条件计数：用包含排斥原理、对称筛公式、棋盘多项式处理。
对称等价计数：用 Burnside 引理和 Polya 定理处理。

前半章的关键词是“坏性质”和“扣回交集”，后半章的关键词是“群作用”“不动点”“轨道”“循环结构”。

本站页面编号是 0122，但课件与习题内部称为“第二十三章/习题二十三”。下面答案按教材题号写成 23.1-23.31。

2、包含排斥原理

设全集为 S，性质 P_i 对应的集合为 A_i。

至少具有一个性质

1
2
3
4
5
|A_1 union ... union A_m|
= sum |A_i|
  - sum |A_i cap A_j|
  + sum |A_i cap A_j cap A_k|
  - ...

不具有任何性质

1
2
3
4
5
6
|S - (A_1 union ... union A_m)|
= |S|
  - sum |A_i|
  + sum |A_i cap A_j|
  - sum |A_i cap A_j cap A_k|
  + ...

做容斥题的关键：先把“坏性质”列出来，再决定要求的是并集还是补集。

典型模板：

1
2
3
4
5
1. 全部方案数 |S|。
2. A_i：违反第 i 个限制的方案。
3. 算单个坏集合、两两交集、三重交集...
4. 按符号交替加减。
5. 检查哪些交集实际上为空。

3、对称筛公式与棋盘多项式

当不同性质影响对称时，可以把交集大小写成统一的 N_k。

若任意 k 个性质同时出现的元素数都是 N_k，则不具有任何性质的元素数为：

1
N - C(m,1)N_1 + C(m,2)N_2 - ... + (-1)^m C(m,m)N_m

错位排列

错位排列数 D_n 表示 n 个元素没有任何一个留在自然位置的排列数。

1
D_n = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!)

递推：

1
2
D_0=1, D_1=0
D_n=(n-1)(D_(n-1)+D_(n-2))

恰有 k 个元素在自然位置：

1
C(n,k)D_(n-k)

棋盘多项式

把禁区看成棋盘。设 r_k 为在禁区中放 k 个互不同行、互不同列棋子的方案数，棋盘多项式：

1
R(C)=r_0+r_1*x+r_2*x^2+...+r_n*x^n

有禁区的排列数为：

1
n! - r_1*(n-1)! + r_2*(n-2)! - ... + (-1)^n*r_n

两个常用性质：

1
2
R(C)=xR(C_i)+R(C_l)
R(C)=R(C_1)R(C_2)      若 C_1、C_2 无公共行列

4、Burnside 引理

设群 G 作用在方案集合 X 上，不同方案按对称变换等价。轨道数为：

1
M = (1/|G|) * sum_{g in G} |Fix(g)|

其中：

1
Fix(g) = 在变换 g 下保持不变的方案集合

做题步骤：

1
2
3
4
5
1. 确定方案集合 X。
2. 确定对称群 G。
3. 按变换类型分类。
4. 求每类变换的不动方案数。
5. 取平均。

5、Polya 定理

Polya 定理常用于着色问题。设 G 作用在 n 个被着色位置上，g 的循环个数为 c(g)，用 m 种颜色着色，则不同着色方案数为：

1
M = (1/|G|) * sum_{g in G} m^(c(g))

如果要记录颜色数量限制，用带权版本。令每种颜色的权为变量，长度为 k 的循环贡献：

1
W_k = color_1^k + color_2^k + ... + color_m^k

再把每个置换的循环结构代入，最后取目标项系数。

Burnside 引理的群通常直接作用在“方案集合”上；Polya 定理的群通常作用在“被涂色的位置”上。位置对称很清楚时，Polya 往往更省事。

6、轮换指数

若 sigma in S_n 的循环结构为：

1
1^c1 2^c2 ... n^cn

也就是有 c_i 个长度为 i 的轮换，满足：

1
c1+2c2+...+ncn=n

同一共轭类中的置换数为：

1
n! / (c1! c2! ... cn! * 1^c1 2^c2 ... n^cn)

一个 k 轮换可写成 k-1 个对换，所以置换奇偶性由：

1
sum (k-1)c_k

决定，等价于由偶长度轮换个数之和：

1
c2+c4+c6+...

决定。

7、习题二十三答案速查

23.1、不能被 4、5、6 整除

在 1-10000 中：

1
2
3
4
5
6
7
floor(10000/4)=2500
floor(10000/5)=2000
floor(10000/6)=1666
floor(10000/20)=500
floor(10000/12)=833
floor(10000/30)=333
floor(10000/60)=166

答案：

1
10000-(2500+2000+1666)+(500+833+333)-166=5334

23.2、既不是平方数也不是立方数

答案：

1
2
3
4
5
平方数：100 个
立方数：21 个
既是平方又是立方，即六次方：4 个

10000-(100+21)+4=9883

23.3、不能被 7 整除但能被 3 或 5 整除

答案：

1
2
3
4
5
1-500 中能被 3、5 或 7 整除的数：
166+100+71-(33+23+14)+4=271

其中能被 7 整除的数：71
所以答案：271-71=200

也可以直接算：

1
|A_3 union A_5| - |(A_3 union A_5) cap A_7|

23.4、多重集 10 组合

1
S={infty*a, 3*b, 5*c, 7*d}

先放开上界：

1
C(4+10-1,10)=C(13,10)=286

坏情况：

1
2
3
4
b 至少 4 个：C(9,6)=84
c 至少 6 个：C(7,4)=35
d 至少 8 个：C(5,2)=10
b 至少 4 且 c 至少 6：1

答案：

1
286-(84+35+10)+1=158

23.5、方程 x1+x2+x3=14

答案：

1
2
3
4
5
(1) 非负整数解，且 xi<=8：
    C(16,14)-3*C(7,5)=120-63=57

(2) 正整数解，且 xi<=8：
    57-9=48

第二问从第一问扣掉含 0 的解。若某个变量为 0，另外两个变量只能是：

1
(6,8), (7,7), (8,6)

共有 3*3=9 个。

23.6、7 本书重新放回书架

答案：

1
2
3
4
5
6
7
8
9
10
(1) 没有一本在原位置：
    D_7=1854

(2) 至少一本在原位置：
    7!-D_7=5040-1854=3186

(3) 至少两本在原位置：
    7!-D_7-7D_6
    =5040-1854-7*265
    =1331

23.7、恰有 k 个数在自然位置

答案：

1
C(n,k)D_(n-k)

先选自然位置上的 k 个数，剩下 n-k 个数做错位排列。

23.8、错位排列分解恒等式

要证：

1
n! = C(n,0)D_n + C(n,1)D_(n-1) + ... + C(n,n)D_0

证明思路：按“恰有 k 个元素在自然位置”对全部 n! 个排列分类。第 k 类有：

1
C(n,k)D_(n-k)

相加即得。

23.9、错位排列奇偶性

结论：

1
D_n 为偶数，当且仅当 n 为奇数。

等价说：

1
D_n 为奇数，当且仅当 n 为偶数。

证明可用递推：

1
D_n=(n-1)(D_(n-1)+D_(n-2))

并从 D_0=1, D_1=0 归纳。

23.10、多重集排列且同类字母不能全相邻

1
S={3*a, 4*b, 2*c}

总排列数：

1
9!/(3!4!2!)=1260

设坏事件为：

1
2
3
A：aaa 全相邻
B：bbbb 全相邻
C：cc 全相邻

各项：

1
2
3
4
5
6
7
8
|A|=7!/(4!2!)=105
|B|=6!/(3!2!)=60
|C|=8!/(3!4!)=280

|A cap B|=4!/2!=12
|A cap C|=6!/4!=30
|B cap C|=5!/3!=20
|A cap B cap C|=3!=6

答案：

1
1260-(105+60+280)+(12+30+20)-6=871

23.11、证明 Qn=Dn+Dn-1

由错位排列公式：

1
D_n=n!(1-1/1!+1/2!-...+(-1)^n/n!)

与 D_(n-1) 相加，交错项抵消后得到题设的 Q_n 形式。

23.12、4 x 4 棋盘选两个不同行不同列方格

答案：

1
2
3
C(16,2)-8*C(4,2)
=120-48
=72

解释：从 16 个方格任选 2 个，再扣掉同行或同列的情况。

23.13、棋盘多项式性质

答案：

1
(1) R(C)=xR(C_i)+R(C_l)

解释：选定一个方格。放棋子在该方格时，删除它所在行列，贡献 xR(C_i)；不放时，贡献 R(C_l)。

1
(2) R(C)=R(C_1)R(C_2)

当 C_1 和 C_2 没有公共行列时，在两个棋盘中放棋子互不影响，棋子数按卷积相乘。

23.14、计算棋盘多项式

题目给定棋盘的棋盘多项式为：

1
R(C)=1+6x+7x^2+x^3

23.15、4 个人分配 5 项工作

可承担关系：

1
2
3
4
x1 -> y1 或 y3
x2 -> y2 或 y5
x3 -> y2 或 y4
x4 -> y3

对应棋盘多项式：

1
1+7x+16x^2+13x^3+3x^4

答案：

1
r_4=3

也可直接列：

1
2
3
4
x4 固定做 y3
x1 只能做 y1
x2、x3 在 y2,y5 或 y2,y4 中避开重复
共 3 种

23.16、排列 A-H 且不出现 BEG、CAD

把 BEG 或 CAD 看成连续块。

答案：

1
8! - 2*6! + 4! = 38904

23.17、15 个人分到 3 个不同房间且每房至少 1 人

答案：

1
3^15 - 3*2^15 + 3 = 14250606

等价写法：

1
3! * {15 3}

其中 {15 3} 是第二类 Stirling 数。

23.18、数字包含与数字构成

题目范围为 1-1000000。

第一问：包含数字 1,2,3,4。把 1-1000000 看作长度 6 的带前导零串，再扣掉不含某些数字的串：

1
2
10^6 - C(4,1)9^6 + C(4,2)8^6 - C(4,3)7^6 + C(4,4)6^6
=231606

第二问：只由数字 1,2,3,4 构成。1000000 不符合要求，位数从 1 到 6：

1
4+4^2+4^3+4^4+4^5+4^6=5460

23.19、S4 的共轭类与轮换指数

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1^4:
(1)

1^2 2^1:
(12),(13),(14),(23),(24),(34)

2^2:
(12)(34),(13)(24),(14)(23)

1^1 3^1:
(123),(124),(134),(234),(132),(142),(143),(243)

4^1:
(1234),(1324),(1243),(1342),(1423),(1432)

23.20、置换奇偶性与偶长轮换数

一个 k 轮换可写成 k-1 个对换。因此置换 sigma 的奇偶性由：

1
sum_{k=1}^n (k-1)c_k

决定。奇数长度轮换贡献偶数，偶数长度轮换贡献奇数，所以奇偶性与：

1
c2+c4+c6+...

一致。

23.21、共轭类中置换个数

若轮换指数为：

1
1^c1 2^c2 ... n^cn

则共轭类大小为：

1
N = n! / (c1! c2! ... cn! * 1^c1 2^c2 ... n^cn)

解释：先把 n 个符号放入轮换槽位有 n! 种；同长度轮换可交换，要除以 c_i!；每个 i 轮换内部有 i 种起点表示，要除以 i^c_i。

23.22、共轭类大小归一恒等式

要证：

1
sum 1/(c1! c2! ... cn! * 1^c1 2^c2 ... n^cn) = 1

其中求和遍历：

1
c1+2c2+...+ncn=n

证明：由 23.21，所有共轭类大小之和为 n!，两边同时除以 n! 即可。

23.23、S4 的所有不变置换类

答案：

1
2
3
4
Z1={(1),(23),(24),(34),(234),(243)}
Z2={(1),(13),(14),(34),(134),(143)}
Z3={(1),(12),(14),(24),(124),(142)}
Z4={(1),(12),(13),(23),(123),(132)}

这里 Z_k 表示使 k 不动的置换集合。

23.24、不变置换类是子群

设：

1
Z_k={sigma in G | sigma(k)=k}

证明：

1
2
(1) 恒等置换在 Z_k 中。
(2) 若 sigma,tau in Z_k，则 sigma*tau^(-1)(k)=sigma(k)=k。

所以由子群判定定理：

1
Z_k <= G

23.25、G 只有恒等置换时的着色数

若：

1
G={(1)}

则没有任何非平凡对称需要合并，用 m 种颜色涂 n 个位置：

1
m^n

23.26、G=Sn 时的着色数

当：

1
G=S_n

所有位置完全对称。不同方案只由每种颜色用了多少个位置决定。

答案：

1
C(n+m-1,n)

也可由 Polya 定理写成：

1
(1/n!) * sum_{k=1}^n [n k] m^k = C(n+m-1,n)

其中 [n k] 是第一类 Stirling 数。

23.27、用非负整数解模型重解 23.26

设 x_i 表示颜色 i 被使用的位置数。则：

1
2
x1+x2+...+xm=n
xi>=0

非负整数解个数为：

1
C(n+m-1,n)

与 23.26 的 Polya 结果一致。

23.28、立方体八个顶点着色

立方体作用在 8 个顶点上的旋转群有 24 个置换。循环结构分类：

1
2
3
4
5
1 个：1^8
6 个：4^2
3 个：2^4
6 个：2^4
8 个：1^2 3^2

黑白两色时：

1
2
(1/24)(2^8 + 6*2^2 + 9*2^4 + 8*2^4)
=23

用 m 种颜色时：

1
(1/24)(m^8 + 17m^4 + 6m^2)

因此对任意正整数 n：

1
24 | (n^8+17n^4+6n^2)

因为它等于合法着色方案数的 24 倍。

23.29、七结点树的黑白着色

题目允许交换每个结点的左右子树。对应置换群有 8 个元素，按 Polya 定理计算：

1
2
N=(1/8)(2^7 + 2*2^6 + 2^5 + 2*2^4 + 2*2^3)
=42

答案：

1
42

23.30、立方体六个面黑白着色

立方体作用在 6 个面上的旋转群循环结构：

1
2
3
4
5
1 个：1^6
6 个：1^2 4^1
3 个：1^2 2^2
8 个：3^2
6 个：2^3

带权 Polya 代入：

1
2
3
4
W1=b+w
W2=b^2+w^2
W3=b^3+w^3
W4=b^4+w^4

清单公式化简后：

1
2
S = b^6 + b^5w + 2b^4w^2 + 2b^3w^3
    + 2b^2w^4 + bw^5 + w^6

答案：

1
2
3
4
5
(1) 三黑三白：2
(2) 四黑二白：2
(3) 不限制黑白数：10
(4) m 种颜色、不限制：
    (1/24)(m^6+3m^4+12m^3+8m^2)

23.31、8 尺木棍相邻不同色

若不考虑翻转对称，方案数为：

1
m(m-1)^7

木棍翻转群只有两个元素：

1
2
(1)
(18)(27)(36)(45)

由于相邻两尺不能同色，翻转不可能固定任何合法着色，因此 Burnside 平均为：

1
N = m(m-1)^7/2

8、复盘清单

1
2
3
4
5
6
7
8
1. 容斥题先列坏性质，再决定求并集还是补集。
2. 多重集限制题用“至少超过上界”作为坏性质。
3. 错位排列记住 D_n 公式、递推和 C(n,k)D_(n-k)。
4. 棋盘多项式题先数 r_k，再代入有禁区排列公式。
5. Burnside 题按变换类型求不动方案数。
6. Polya 题先写循环结构，再代入颜色数或权重。
7. 立方体题要分清作用在顶点、边还是面上。
8. 带颜色数量限制时用带权 Polya，读对应项系数。