Chap20 计数原则、排列组合与组合恒等式

返回：0100 离散数学课程总目录 · 上一章：0119 组合数学引言、鸽巢原理与 Ramsey 定理 · 下一章：0121 递推方程与生成函数

1、学习目标

本章是组合计数的基础工具箱。核心不是背一堆公式，而是先分清：分类还是分步、有序还是无序、重复还是不重复、盒子是否有区别、限制是否有上界。

主线：

加法法则：互斥分类。
乘法法则：连续分步。
排列组合：有序/无序，不重复选取。
多重集：对象允许重复。
二项式定理：处理组合数、展开式系数和求和。
多项式定理：处理多类对象分配与多项式系数。
非降路径：用格路模型证明组合恒等式。

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

2、两个计数原则

加法法则

若完成一件事可以分成互不重叠的 k 类，第 i 类有 n_i 种方法，则总数为：

1	n1+n2+...+nk

适用关键词：

1	或者、分类、按情况讨论、互斥。

乘法法则

若完成一件事要依次做 k 步，第 i 步有 n_i 种方法，则总数为：

1	n1n2...*nk

适用关键词：

1	先...再...、分步、每一步独立选择。

典型例子：

1400 = 2^3 * 5^2 * 7
正因子形如 2^i 5^j 7^k
其中 0<=i<=3, 0<=j<=2, 0<=k<=1
所以正因子个数为 (3+1)(2+1)(1+1)=24。

3、排列组合模型

设从 n 元集合中选 r 个元素。

模型	公式	识别方式
集合排列	`P(n,r)=n!/(n-r)!`	有序，不重复
集合组合	`C(n,r)=P(n,r)/r!=n!/(r!(n-r)!)`	无序，不重复
可重复有序选择	`n^r`	每个位置独立选择
多重集 r 组合	`C(k+r-1,r)`	`k` 类元素，无序，允许重复
r 环排列	`P(n,r)/r=n!/(r(n-r)!)`	选 `r` 个排成环，旋转视为相同

常用等式：

C(n,r)=C(n,n-r)
C(n,r)=C(n-1,r)+C(n-1,r-1)
k*C(n,k)=n*C(n-1,k-1)
(n-k)*C(n,k)=n*C(n-1,k)

4、多重集排列与组合

多重集写作：

1	S={n1a1, n2a2, ..., nk*ak}

若总数：

1	n=n1+n2+...+nk

全排列数为：

1	n!/(n1! n2! ... nk!)

若每类元素数量足够多，k 类元素取 r 个做无序组合，则等价于非负整数解：

1	x1+x2+...+xk=r

方案数为：

1	C(k+r-1,r)

放球模型：

r 个相同球放入 n 个不同盒子，允许空盒：
C(n+r-1,r)

r 个相同球放入 n 个不同盒子，不允许空盒：
C(r-1,n-1)

r 个相同球放入 n 个不同盒子，每盒至少 q 个：
C(r-nq+n-1,n-1)

5、二项式定理与组合恒等式

二项式定理：

1	(x+y)^n = sum_{k=0}^n C(n,k) x^(n-k) y^k

常用形式：

1	(1+x)^n = sum_{k=0}^n C(n,k)x^k

常用求和：

sum_{k=0}^n C(n,k)=2^n
sum_{k=0}^n (-1)^k C(n,k)=0
sum_{k=0}^n k*C(n,k)=n*2^(n-1)
sum_{k=0}^n (k+1)*C(n,k)=2^(n-1)(n+2)
sum_{k=0}^n C(n,k)r^k=(1+r)^n

Vandermonde 恒等式：

1	sum_{k=0}^r C(m,k)C(n,r-k)=C(m+n,r)

组合恒等式证明常用方法：

1. 公式代入；
2. 二项式定理，必要时令 x=1、x=-1、x=2；
3. 求导或积分；
4. 组合解释：两边计数同一个集合；
5. 非降路径模型。

6、多项式定理

多项式定理：

1 2	(x1+x2+...+xt)^n = sum n!/(n1!n2!...nt!) * x1^n1x2^n2...*xt^nt

其中求和遍历所有非负整数解：

1	n1+n2+...+nt=n

多项式系数：

1	C(n; n1,n2,...,nt)=n!/(n1!n2!...nt!)

组合含义：

1
2
3

1. n 个不同球放入 t 个不同盒子，第 i 个盒子恰好 n_i 个球。
2. n 元集划分成 t 个有序子集，第 i 个子集恰好 n_i 个元素。
3. 多重集 {n1*a1,...,nt*at} 的全排列数。

展开式不同项数：

1	C(n+t-1,n)

展开式所有系数之和：

t^n

7、非降路径模型

从 (0,0) 到 (a,b) 的非降路径，只允许向右和向上走，路径数为：

1	C(a+b,a)=C(a+b,b)

常见用法：

1
2
3

1. 按必经点分类，证明卷积恒等式。
2. 按首次穿越/反射路径，计算不过对角线的路径数。
3. 把组合数求和转成终点固定、经过点变化的路径计数。

8、习题二十一答案速查

21.1、5 道工序排列

答案：

1
2
3

(1) P(5,5)=120
(2) 某工序必须先加工：P(4,4)=24
(3) 某工序不能最后加工：P(5,5)-P(4,4)=96

21.2、100 件产品抽 3 件

答案：

1
2
3

(1) C(100,3)=161700
(2) 恰有 1 件次品：C(2,1)C(98,2)=9506
(3) 至少 1 件次品：C(100,3)-C(98,3)=9604

21.3、纪念章和纪念册赠送

10 位同学每人得一件。

答案：

1 2	(1) 纪念章和纪念册都不同：P(10,10)=10! (2) 4 枚章相同、6 本册相同：C(10,4)=210

第二问只需选出哪 4 位同学拿纪念章。

21.4、从 1 到 100 选两个数

答案：

1 2	(1) 差恰好为 7：93 (2) 差不超过 7：sum_{r=1}^7 (100-r)=672

21.5、8 x 8 棋盘选相邻方格

答案：

1
2
3

横向相邻：8*7=56
纵向相邻：8*7=56
总数：112

21.6、字母排列

排列 a,b,c,d,e,f。

答案：

1 2	(1) b 紧跟在 e 左边：把 eb 看作一个整体，5!=120 (2) b 在 e 左边：6!/2=360

21.7、两排座位

两排各 8 个座位，14 个学生；其中 5 人总坐前排，4 人总坐后排。

答案：

1	C(8,5)5!C(8,4)4!C(7,5)*5!

解释：先安排指定前排 5 人，再安排指定后排 4 人，剩下 5 人坐剩余 7 个座位。

21.8、红皮书与黑皮书

9 本不同的书，4 本红皮，5 本黑皮。

答案：

(1) 任意排列：9!
(2) 黑皮书都相邻：5!*5!
(3) 黑皮相邻且红皮相邻：2*5!*4!
(4) 黑皮和红皮相间：5!*4!

第四问因为黑皮书多 1 本，排列形状只能是：

黑 红 黑 红 黑 红 黑 红 黑

21.9、24 卷百科全书选 5 卷不相继

设选出的卷号：

1	i1<i2<...<i5

且相邻选中卷号不连续。令：

kj=ij-j+1

则转成从 {1,2,...,20} 中选 5 个。

答案：

C(20,5)

21.10、圆排列

从 {1,2,...,n} 中任选 m 个排成圆圈。

线排列数：

1	P(n,m)=n!/(n-m)!

同一个圆排列对应 m 个线排列，因此：

1	n!/(m*(n-m)!)

21.11、最大元素分类

考虑 {1,2,...,n+1} 的非空子集。

答案：

1 2	(1) 最大元素恰好为 j 的非空子集数为 2^(j-1)。 (2) 1+2+2^2+...+2^m = 2^(m+1)-1。

证明思路：最大元素为 j 时，j 必选，1..j-1 可任意选。

21.12、汽车安全与防污染试验

答案：

1
2
3

(1) C(200,30)*C(200,30)
(2) 正好 5 辆同时做两种试验：
    C(200,5)*C(195,25)*C(170,25)

第二问：先选重叠的 5 辆，再选只做安全的 25 辆，最后选只做防污染的 25 辆。

21.13、15 名运动员分成 3 组

答案：

(1) 分配到有名称的 A,B,C 三组：
    C(15,5)C(10,5)C(5,5)

(2) 分成 3 个无名称小组：
    C(15,5)C(10,5)C(5,5)/3!

21.14、选 8 名代表

三年级和四年级各 50 人；每个年级 25 男、25 女。选 8 人，要求 4 女、3 名低年级。

按低年级女生人数分类，答案可写为：

1 2	N = 2C(25,3)C(25,1)C(25,4) + 2C(25,2)^2C(25,1)C(25,3)

也就是：

1	N = 50C(25,3)(C(25,4)+C(25,2)^2)

21.15、从 1 到 1000 选 3 个数，和被 4 整除

按模 4 余数分类，每类各 250 个。

答案：

1 2	C(250,3)+3C(250,2)C(250,1)+C(250,1)^3 = 41541750

21.16、扑克牌选 5 张

从去掉大小王的 52 张牌中选 5 张。

答案：

(1) 没有 A 但有 2 张 K：
    C(4,2)*C(44,3)

(2) 有红桃 A，其他 4 张牌是顺子：
    11*4^4 - 4^3 - 4^3 = 2688

21.17、有序三元组与平方和

设 S={1,2,...,n+1}，选择有序三元组 <x,y,z>，要求 z>x 且 z>y。

答案：

(1) 若 z=k+1，则 x,y 各有 k 种选择，共 k^2 个。
(2) 按 x=y、x<y、x>y 分成 A,B,C：
    |A|=C(n+1,2)
    |B|=|C|=C(n+1,3)
(3) 1^2+2^2+...+n^2 = C(n+1,2)+2*C(n+1,3)

21.18、多重集各种大小子集总数

若：

1	S={n1a1, n2a2, ..., nk*ak}

选择 ai 的个数可以是 0..ni，所以子集总数为：

1	(n1+1)(n2+1)...(nk+1)

21.19、部分元素无限重的 r 组合

设：

1	S={1a1,...,1at, infinitya_{t+1},...,infinityak}

答案：

1	sum_{i=0}^r C(t,i)*C(k-t+r-i-1,r-i)

含义：先从前 t 个只能取 0/1 次的元素中选 i 个，再从后 k-t 个无限重元素中取 r-i 个。

21.20、红黄白球排列

红球 4 个，黄球 3 个，白球 3 个，排成直线。

答案：

1	10!/(4!3!3!)

21.21、0/1/2 排列且相邻不同

从 {infinity*0, infinity*1, infinity*2} 中取 n 个数作排列，要求相邻位置不同。

答案：

第 1 位有 3 种选法；
后面每位不能等于前一位，各有 2 种。

总数：3*2^(n-1)

21.22、非降数字正整数

小于 10^n 且各位数字从左到右非降的正整数个数：

1	C(n+9,9)-1

解释：等价于从 {infinity*0,...,infinity*9} 中取 n 个数字后按非降排列，排除全 0。

21.23、22 本书分给 5 个学生

其中 2 名学生各得 5 本，另外 3 名各得 4 本。

答案：

1	C(5,2)C(22,5)C(17,5)C(12,4)C(8,4)*C(4,4)

最后 C(4,4)=1 可省略。

21.24、相同球放入不同盒

答案：

(1) r 只相同球放入 n 个不同盒子，无空盒：
    C(r-1,n-1)

(2) 每盒至少 q 个：
    C(r-nq+n-1,n-1)

第二问令 yi=xi-q，转成：

1	y1+...+yn = r-nq, yi>=0

21.25、多重集的 3 排列和 3 组合

多重集：

1	{2a,1b,3*c}

所有 3 组合：

1	{a,a,b}, {a,a,c}, {a,b,c}, {a,c,c}, {b,c,c}, {c,c,c}

所有 3 排列：

aab, aba, baa,
aac, aca, caa,
abc, acb, bac, bca, cab, cba,
acc, cac, cca,
bcc, cbc, ccb,
ccc

21.26、由 1,1,2,3,3,4 组成的 4 位数

答案：

按 4 组合分类：

6 类形如 {重复,重复,单,单}，各有 4!/2! 种；
1 类 {1,2,3,4}，有 4! 种；
1 类 {1,1,3,3}，有 4!/(2!2!) 种。

6*12+24+6=102

21.27、展开 `(2x-y)^7`

答案：

1
2
3

(2x-y)^7
= 128x^7 - 448x^6y + 672x^5y^2 - 560x^4y^3
  + 280x^3y^4 - 84x^2y^5 + 14xy^6 - y^7

21.28、`(3x-2y)^18` 的系数

答案：

x^5 y^13 的系数：
-C(18,5)*3^5*2^13

x^8 y^9 的系数：
0

第二个为 0，因为 x^8y^9 总次数是 17，不可能出现在 18 次齐次展开式中。

21.29、证明 `sum C(n,k)2^k=3^n`

由二项式定理：

1	(1+2)^n = sum_{k=0}^n C(n,k)2^k = 3^n

21.30、证明交错二项式和

结论：

1	sum_{k=0}^n (-1)^k C(n,k)3^(n-k)=2^n

由：

1	(3-1)^n = sum_{k=0}^n C(n,k)3^(n-k)(-1)^k

即可。

21.31、组合恒等式四题

答案：

(1) sum_{k=1}^{n+1} (1/k)*C(n,k-1)
    = (2^(n+1)-1)/(n+1)

(2) sum_{k=0}^n (k+1)*C(n,k)
    = 2^(n-1)(n+2)

(3) sum_{k=0}^n (2^(k+1)/(k+1))*C(n,k)
    = (3^(n+1)-1)/(n+1)

(4) sum_{k=1}^n (-1)^(k-1)*(1/k)*C(n,k)
    = 1+1/2+...+1/n

证明方法：

1
2
3

(1)(3)：对 (1+x)^n 积分，再取 x=1 或 x=2。
(2)：拆成 sum k*C(n,k)+sum C(n,k)。
(4)：用归纳法，或由 32(2) 递推推出。

21.32、求和三题

答案：

(1) sum_{k=0}^n C(n,k) r^k = (1+r)^n

(2) sum_{k=0}^n (-1)^k * C(n,k)/(k+1) = 1/(n+1)

(3) sum_{k=0}^n C(2n-k,n-k) = C(2n+1,n)

第三问令 j=n-k，变成：

1	sum_{j=0}^n C(n+j,j)=C(2n+1,n)

21.33、带分母的交错和

要证：

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

证明方法：对 m 归纳，或把：

1/(m+k+1)

看成积分中的指数项，利用二项式展开。

21.34、乘积型求和

结论：

1 2	sum_{k=0}^{n-1} C(n,k)*C(n,k+1) = (2n)!/((n-1)!(n+1)!)

等价写法：

C(2n,n-1)

可用 Vandermonde 恒等式证明。

21.35、交错分母和

结论：

1 2	sum_{k=1}^n (-1)^(k-1)*C(n,k)/(k+1) = n/(n+1)

由 32(2)：

1	sum_{k=0}^n (-1)^k*C(n,k)/(k+1)=1/(n+1)

移去 k=0 项即可。

21.36、平方权重求和

结论：

1 2	sum_{k=2}^{n-1} (n-k)^2*C(n-1,n-k) = n(n-1)2^(n-3) - (n-1)^2

证明使用教材公式：

1 2	sum kC(n,k)=n2^(n-1) sum k^2C(n,k)=n(n+1)2^(n-2)

并做变量替换。

21.37、两类求和

答案：

1
2
3

(1) sum_{k=0}^m C(n-k,m-k)=C(n+1,m)

(2) sum_{k=0}^m C(u,k)C(v,m-k)=C(u+v,m)

第二问就是 Vandermonde 恒等式。

21.38、展开 `(x1+x2+x3)^4`

用多项式定理：

(x1+x2+x3)^4
= x1^4+x2^4+x3^4
 +4*(x1^3x2+x1^3x3+x2^3x1+x2^3x3+x3^3x1+x3^3x2)
 +6*(x1^2x2^2+x1^2x3^2+x2^2x3^2)
 +12*(x1^2x2x3+x2^2x1x3+x3^2x1x2)

21.39、确定多项式系数

求：

1	(x1-x2+2x3-2x4)^8

中：

1	x1^2 x2^3 x3 x4^2

项的系数。

答案：

1 2	8!/(2!3!1!2!) * 1^2 * (-1)^3 * 2^1 * (-2)^2 = -13440

21.40、多项式系数交错和

第一问：

1	sum (-1)^(a+b) * C(n; a,b,c,d)=0

其中求和遍历：

a+b+c+d=n

证明：这是：

1	(-x1-x2+x3+x4)^n

令：

1	x1=x2=x3=x4=1

时的所有系数和，即：

1	(-1-1+1+1)^n=0

一般化：若有偶数个变量，一半取负一半取正，则：

1	sum (-1)^(r1+...+rk)*C(n;r1,...,r_{2k})=0

其中：

1	r1+...+r_{2k}=n

21.41、证明 `C(2p,p)` 模 p 余 2

设 p 是奇素数。利用：

1	C(2p,p)=sum_{k=0}^p C(p,k)C(p,p-k)

当 0<k<p 时：

1	p \| C(p,k)

所以中间项都被 p 整除，只剩两端：

1	C(p,0)C(p,p)+C(p,p)C(p,0)=2

因此 C(2p,p) 被 p 除的余数为 2。

21.42、不同球放入不同盒

把 n 个有区别的球放入 t 个有区别的盒子，第 i 个盒子恰好 n_i 个球。

答案：

1	C(n; n1,n2,...,nt)=n!/(n1!n2!...nt!)

证明：先选盒 1 的 n1 个球，再选盒 2 的 n2 个球，依次使用乘法法则。

21.43、n 元集划分成有序子集

把 n 元集划分成 t 个有序子集，允许空子集，且第 i 个子集有 n_i 个元素。

答案同 21.42：

1	C(n; n1,n2,...,nt)

21.44、多项式系数与 Fermat 小定理

第一问：若 p 为素数，且多项式系数：

1	C(p; n1,n2,...,nt) != 1

则：

1	p \| C(p; n1,n2,...,nt)

原因：若系数不等于 1，则所有 n_i<p，分母的阶乘不含因子 p，而分子含一个因子 p。

第二问：把：

n^p

写成：

1	(1+1+...+1)^p

展开。除了 n 个系数为 1 的纯项外，其余项系数都被 p 整除，所以：

1	p \| (n^p-n)

这就是 Fermat 小定理。

21.45、用非降路径证明三条恒等式

三条恒等式：

(1) sum_{k=0}^r C(m,k)C(n,r-k)=C(m+n,r)

(2) sum_{l=0}^n C(l+k,k)=C(n+k+1,k+1)

(3) sum_{l=0}^k C(n+l,l)=C(n+k+1,k)

证明思路：把等式右边看成从 (0,0) 到某个终点的非降路径总数；左边按路径经过的某条竖线或横线上的点分类。

21.46、非降路径证明卷积

要证：

1	sum_{k=0}^m C(n-k,m-k)C(r+k,k)=C(n+r+1,m)

路径解释：右边计数从：

1	(0,0) 到 (n+r+1-m,m)

的非降路径。左边按路径经过：

1	(r,k) -> (r+1,k)

这一横向步骤的位置分类。

21.47、不过直线 y=x 的非降路径

从 (0,0) 到 (n,n) 的非降路径总数：

C(2n,n)

用反射法，穿过对角线的一侧路径数为：

C(2n,n-1)

答案中上下两侧都计入，因此不过对角线的非降路径数为：

1 2	2(C(2n,n)-C(2n,n-1)) = 2/(n+1)C(2n,n)

9、复盘清单

1. 看到“或者”先想加法法则，看到“先后”先想乘法法则。
2. 先判断有序/无序，再判断重复/不重复。
3. 分组题先问：组是否有名称？若无名称，通常要除以组的排列数。
4. 相同球放不同盒，优先转成整数解。
5. 二项式求和常用 x=1、x=-1、x=2、求导、积分。
6. 多项式系数就是多类分配和多重集全排列。
7. 非降路径题先找终点，再按必经点或反射路径分类。