组合数学

内容提要：

本章主要介绍加法原理、乘法原理、排列与组合、多重集合的排列与组合、二项式系数以及一些常见的组合恒等式、集合的分划与第2类Stirling数、正整数的分拆（无序分拆和有序分拆）与分配问题等．

排列和组合是人们普遍遇到的、并已被广泛使用的基本概念，只是人们没有从理论上研究它．例如，学生集合站队问题、买水果问题等．如果考虑的对象与秩序有关，则称之为排列问题；如果考虑的对象与秩序无关，则称之为组合问题．除了这种具有普遍意义的排列和组合之外，还有可重复元素的排列和组合问题．为了能深入研究这些问题，下面首先介绍两个最基本最常用的原理．

1.1 加法原理（原则）与乘法原理（原则）

加法原理（原则） 设事件A有m种选取方式，事件B有n种选取方式，选A或B共有m + n种方式．例如，每周在E校区上4节课，在W校区上8节课，除此之外没有别的课，则每周上4 + 8 = 12节课．这里事件A指的是在E校区上4节课，事件B指的是在W校区上8节课，而每周的课不是在E校区就是在W校区，即属于A或B．

如果用集合论的语言描述，则描述如下：

定理1.1.1 设A，B为有限集，AIB = Φ，则| AUB | = |A| + |B|．证明：当A，B中有一个是空集，定理的结论是平凡的． 设A ≠ Φ，B ≠ Φ，记

A = {a1, a 2,L, a m}B = {b1, b 2,L, b n}

并做映射

Ψ：ai →i（1 ≤ i ≤ m）

bj →m+j（1 ≤ j ≤ n）因为

ai ≠ bj (1 ≤ i ≤ m, 1 ≤ j ≤ n)

2组合理论及其应用

所以 是从AUB到集合{1，2，L，m+n}上的一一映射，因而定理成立．推论1.1.1 设n个有限集合S1, S2, L, Sn满足Si ISj = Φ (1≤ i ≠ j ≤ n)则 |USi|=∑|Si|．i=1i=1nn【例1】 在所有6位二进制数中，至少有连续4位是1的有多少个？

解：把所有满足要求的二进制数分成如下3类：

（1）恰有4位连续的1．它们可能是01111，011110，11110×，其中，“”取0或1．故在此种情况下，共有5个不同的6位二进制数．

（2）恰有5位连续的1．它们可能是011111和111110，共有2个．

（3）恰有6位连续的1．即111111，只有1种可能．

综合以上分析，由加法原理知共有5+2+1=8个满足题意要求的6位二进制数．乘法原理（原则） 设事件A有m种选取方式，事件B有n种选取方式，则选取A以后再选取B共有m × n种方式．用集合论的语言可叙述如下：

定理1.1.2 设A，B是两个有限集合，|A| = m，|B| = n，则|A × B| = |A| × |B| = m × n．证明：若m = 0或n = 0，则等式两边均为0，故等式成立． 设m > 0，n > 0，并且记

A = {a1, a2,L, am}，

B = {b1, b2,L, bn}，

定义映射

Ψ：(ai, bj) →（i – 1）n + j (1 ≤ i ≤ m, 1 ≤ j ≤ n)，

则 是A×B到集合{1, 2,L, mn–1, mn}上的一一映射，所以等式成立．

推论1.1.2 设S1, S2, L, Sn为n个有限集合，则|S1 × S2 ×L× Sn| = |S1|×|S2|×L×|Sn|.【例2】 比5400大的4位数中，数字2，9不出现，且各位数字不同的数有多少个？解：比5400大的4位数可以分为4类：

（1）千位比5大的符合题意的整数有3 × 7 × 6 × 5个．（2）千位是5，百位比4大的符合题意的整数有3 × 6 × 5个．（3）前2位是54，十位不为0且符合题意的整数有5 × 5个．（4）前3位是540，个位不为0且符合题意的整数有5个．

故共有3 × 7 × 6 × 5 + 3 × 6 × 5 + 5 × 5 + 5 = 750个符合条件的整数．【例3】 在1000到9999之间有多少个各位数字不同的奇数？

第1章 排列、组合、二项式定理3

解：方法1 如图1.1所示，第4位必须是奇数，可取1，3，5，7，9，共5种选择．第1位不能取0，也不能取第4位已选定的数字，所以在第4位选定后第1位有8种选择．类似地，第2位有8种选择，第3位有7种选择．从而，满足题意的数字共有5 × 8 × 8 × 7 = 2240个．

第1位





第4位

第2位第3位

图 1.1

方法2 把满足题意的数分为两类：

（1）4位数中没有0出现．类似方法1的分析，第4位有5种选择，第3位有8种选择，第2位有7种选择，第1位有6种选择，此类数共有6 × 7 × 8 × 5 = 1680个．

（2）4位数中有0出现，这里，0只能出现在第2位或第3位上．假设0在第2位上，则第4位有5种选择，第3位有8种选择，第1位有7种选择，共有7 × 8 × 5 = 280个数．同理，若0出现在第3位上，也有280个数．

由加法原则知，合乎题意的数共有1680 + 280 × 2 = 2240个．

1.2 排列与组合

本节将探讨一些基本的排列与组合问题．同时，也会做一些延伸，比如圆排列问题．

1.2.1 集合的排列

n元集合S的一个r排列是指先从S中选出r个元素，然后将其按次序排列．一般用 P（n, r）或Pnr表示n元集合S的r排列数．

例如，设S={a,b,c}，则

ab, ac, ba, bc, ca, cb

是S的所有6个2排列，所以P(3, 2) = 6．当r = n时，称n元集合S的n排列为S的全排列，即P(n, n) = n!，相应的数称为n元集合S的全排列数，如S = {a, b, c}，则abc, acb, bac, bca, cab, cba

是S的所有6个全排列，所以P(3, 3) = 6．

显然，有

（1）P (n, r) = 0（2）P (n, 1) = n

(r > n)；(n ≥ 1)．

定理1.2.1 对于满足r ≤ n的正整数n和r，有P (n, r) = n (n – 1)L(n – r + 1) = n! / (n – r)!．证明：要构造n元集合的一个r排列，可以在n元集合中任取一个作为第1项，有n种取法；在取定第1项后，第2项可以从剩下的n – 1个元素中任选一个作为第2项，有 n – 1种取法；同理，在前r – 1项取定后，第r项有n – r + 1种取法．由乘法原理知：

P (n, r) = n (n – 1)L(n – r + 1) = n! / (n – r)!

由定理1.2.1，n元集合的全排列数P(n, n)= n!. 规定：0! = 1．【例4】 有4盏颜色不同的灯：

4组合理论及其应用

（1）把它们按不同的次序全部挂在灯杆上表示信号，共有多少种不同的信号？（2）每次使用1盏、2盏、3盏或4盏灯按一定的次序挂在灯杆上表示信号，共有多少种不同的信号？

解：（1）P (4, 4) = 24.

（2）P (4, 1) + P (4, 2) +P (4, 3) + P (4, 4) = .【例5】 将a, b, c, d, e, f进行排列．问：

（1）使得字母b正好在字母e的左邻的排列有多少种？（2）使得字母b在字母e的左边的排列有多少种？

解：（1）b正好是e的左邻，那么把be看作一个字母E，则原问题就变成求集合{a, c, E, d, f }的全排列数，共有5！种排列．

（2）将{a, b, c, d, e, f }的所有全排列分成如下两类：

A = {× ×L× | 其中b在e的左边}，B = {× ×L× | 其中b在e的右边}．

显然有AIB = Φ，AUB = {a, b, c, d, e, f }的全体全排列，| AUB | = 6!．

定义映射f：A→B，使f（LbLeL）=（LeLbL）.

即f将A中的任一排列的b与e的位置互换，保持其余字母位置不变，得到B中的一个排列．显然，f是一一映射，所以 |A| = |B| = 1/2×6!.

【例6】 现在把例5改一下．从a, b, c, d, e, f中选出3个字母进行排列，且b与e不相邻的排法有多少种？

解：方法1 从6个字母选出3个的排列共有P(6,3)个，将其分为以下3类：（1）b和e挨在一起，且b是e的左邻．（2）b和e挨在一起，且b是e的右邻．

（3）b和e不挨在一起（包括不出现b和e）．

从例5的第2问知道，第1类和第2类的排法是同样多的．现在分析第1种情况．选定了b，e，那么只需从a，c，d，f中再选出1个，与代表b是e的左邻的E进行排列；所以第1种情况共P(4, 1) × P (2, 2)种排法．第2种情况也有P(4, 1) ×P (2, 2)种排法．显然，这里没有其他的可能情况．因此，要求的第3类排法的个数为

P (6, 3) – 2 × P (4, 1) ×P (2, 2) = 104．

方法2 直接计算．满足题意的排列可分为如下4类：

（1）排列中b，e均不出现，即为4元集合{a, c, d, f }的3排列，共有P(4, 3)种．

（2）排列中只出现b，不出现e．那么先从4元集合{a, c, d, f }中选出2个进行排列，然后把b放在它们之间或两端，故此类排法共有3 × P (4, 2)种．

（3）排列中只出现e，不出现b．同（2），此类排法共有3×P (4, 2)种．

（4）排列中出现e和b，但不相邻．显然，需要从集合{a, c, d, f }中选出1个，然后把b和e放在它两边．那么此类排法有2×P (4, 1)种．

所以，共可以得到

P (4, 3) + 3×P (4, 2) + 3×P(4, 2) + 2×P (4, 1) = 104

种符合题意的排法．

第1章 排列、组合、二项式定理5

前面考虑的排列是在直线上进行的，或者更恰当地说，是线性排列—— r线排列．若在圆周上进行排列，结果又如何呢？例如，由R，W，L，G，Y五色扇形组成的圆盘，只要各种颜色间相对位置不变，就是同一个圆盘．有一种可能是下面这样的排列：

R

W L G    Y

而线性排列RWGYL，WGYLR，GYLRW，YLRWG，LRWGY代表的都是这个圆盘．这样可以看出，这五色的循环排列数等于5!/5 = 4!．

现在推广到r圆排列．在1个r圆排列的任意2个相邻元素之间都有一个位置，共有r个位置．从这r个位置处将该圆排列断开，并拉直成线排列，可以得到r个不同的r线排列．也就是说，将r个r线排列

a1a2Lar−1ar

r个aaLaa

23r1

线性L



排列aaLaa

r1r−2r−1

的首尾相连围成圆排列，得到的是同一个r圆排列．因此，下面的定理成立：

定理1.2.2 n元集合S的r圆排列数为P(n,r)n!=．rr(n−r)!特别地，n个元素S的n圆排列数为(n – 1)!．

1.2.2 集合的组合

n

n元集合S的r组合是指从S中取出r个元素的一种无序选择，其组合数记为或

r

rCn．显然，有

定理1.2.3 若0 ≤ r ≤ n，则n元集合S的r组合数为nP(n, r)n!=．=r!r!(n−r)!r证明：设S是一个n元集合，任取S的一个r组合，将该r组合中的r个元素进行排

列，便可得到P(r, r) = r!个S中的r排列．而且S中的任一r排列都可恰好通过将S中的某一r组合排列而得到．所以有

n

P(n, r)=r!⋅，

r

即

6组合理论及其应用

nP(n, r)n!

==.rr!r!(n−r)!

特别的，

nn

（1）=1, =1.

0nn

（2）=0(r>n).

r

【例7】 12个人围坐在圆桌旁，其中一个拒绝与另一个相邻，问有多少种安排方法？解：（1）如果这两个人是确定的：先把其他11个人安排在圆桌旁，共有11!/11种；固定这11人后再把剩下的那个人加以安排，他的位置共9个，所以总的排法为11!/11 × 9 = 9 × 10! 种．

12

（2）如果这两个人是任意的：先选出这两个人来，有种选法；确定这两个人后，

212

排法有11!/11 × 9种．故总的排法有  11!/11 × 9 = 54 × 11!种．

2

【例8】 现有100件产品，其中有两件是次品．如果从中任意抽出3件，抽出的产品中至少有1件次品的概率是多少？

100

解：从100件产品中任意抽出3件，共有种方案；抽出的产品中至少有1件次

3982982

品，有两种情况：只有1件和有两件，分别有种和种方案．所以，所要

2112求的概率为

982298

+

2121×100% = 5.94%

．

1003

【例9】 把q个负号和p个正号排在一条直线上，使得没有两个负号相邻，证明不同

p+1

的排法有种．

q证明：如果p + 1 ≥ q，题目相当于把p个正号排列在一起，然后把q个负号插入( p +

p+1p+1

1)个空隙里，每个空隙插一个．现在这样的排列共有种，故而共有种排法．

qqp+1

如果p+1 < q，显然不可能没有两个负号相邻，记排法为0种．由于此时= 0，

q

p+1

故可以统一地记为．得证．

q

【例10】 取定空间中的25个点，其中任意4个点均不共面，问它们能决定多少个三

第1章 排列、组合、二项式定理7

角形？多少个四面体？

解：既然任意4个点均不共面，那么任意3点也不共线（若有3点共线，则这条线与另外任一点共面）．故任意3点可以组成一个三角形，任意4点可以组成一个四面体．因

2525

=2300而这25个点可以组成的三角形个数为，四面体个数为=12650．34

下面给出两个组合恒等式．

nn推论1.2.1 若0 ≤ r ≤ n，则=.rn−rn

证明：由定理1.2.3中关于的显式表达式很容易得出结论．

rnn

推论1.2.1的组合意释：是n元集合S的r元子集的个数，是n元集合

rn−rS的n – r元子集的个数，设A是S的r元子集，则S – A是S的n – r元子集，而且这种对应关系是一一对应的．所以S的r元子集的个数等于S的(n – r)元子集的个数．

定理1.2.4 对任意正整数n，有nnnnn+++L+=2.012n证明：从两个不同的方面计算n元集合S的所有子集的个数，说明等式左，右两端均

等于S的子集数，从而证明其成立．

n

一方面，S的r元子集的个数为，而r可取0，1，2，L，n，由加法原则，S的

r所有子集的个数为

nnnn

+++L+012n

另一方面，S有n个元素，在构成S的一个子集的时候，S的每个元素都有在该子集中或不在该子集中两种可能，由乘法原则知，共有2n种方式构造S的一个子集，即S的子

集有2n个．

综上分析，得知定理成立．

【例11】 单射函数f ：X→Y的个数等于P(m, n)，其中，n = | X |, m = | Y | ( m ≥ n)．证明：设X = {x1, x2,L, xn}，则f (xi) ∈ Y(i = 1, 2,L, n).因f是单射，所以f (x1), f (x2),L, f (xn)互不相同，故

f (x 1) f (x 2) L f (x n)

是Y的一个n排列．由此易知单射函数f ：X→Y与Y的n排列构成一一对应，其个数为 P(m, n).

由例11知，若| X | = | Y | = n，则一一映射f ：X→Y的个数等于n!．

8组合理论及其应用

【例12】 从整数1，2，L，1000中选取3个数，使它们的和正好被4整除，有多少种选法？

解：1～1000中被4整除余1、余2、余3、余0（即被4整除）的数各有250个．3个数如果都能被4整除，其和自然也能被4整除；同样，一个余0的、一个余1的、一个余3的数之和，或一个余0的、两个余2的数之和，或两个余1的、一个余2的数之和，或两个余3的、一个余2的数之和，都可以被4整除．除此之外没有别的情况可以使题设成立了．故而共有

250250250250250250250250250250+  + + + ＝33 760 5003111122121种选法．

【例13】 某车站有6个入口，每个入口每次只能进一个人，则9人小组共有多少种进站方案？

解：方法1 将6个入口依次排好序，分别为第1，第2，L，第6个入口．因9人进站时在每个入口都是有序的，我们如下构造9人的进站方案：

* *△* △* **△* △* △* 先构造9人的全排列，共有9！个；然后选定9人的一个全 ↑↑ ↑ ↑↑ 3 5 9 11 13排列．加入5个分隔符，将其分成6段，第i（i = 1，2，L，6）段对应着第i个入口的进站方案．如图1.2所示，每个“*”代表一个人，“△”表示分隔符．

故进站方案数为

1414!9!×=×9!=726 485 760.59!×5!方法2 第1个人可以有6种进站方式，即可从6个入口中的任一个进站；第2个人也

可以选择6个入口中的任一个进站，但当他选择与第1人相同的入口进站时，有在第1人前还是后两种方式，所以第2人有7种进站方案；同理，第3人有8种进站方案，……，第9人有14种进站方案．由乘法原则，总的进站方案数为

6 × 7 ×L× 14 = 726 485 760．

【例14】 有8个大小相同的棋子（5个红的、3个蓝的），放在8×8的棋盘上，每行、每列都只能放一个，有多少种放法？

解：我们先放红色的．

8

（1）在8行中任选5行放红色棋子，有种选择．

5

（2）选定行后，再选列．因为每行都不同，故有P(8, 5)种选择．

现在再放蓝色的棋子．还剩3行、3列，而每个棋子都是相同的，故可把第1个棋子放在剩下的第1行，3列可选；第2个棋子放第2行，两列可选；第3个棋子则只剩下1行1列可选．于是，有3!种方案．

8

根据乘法原理，共有 P(8, 5) × 3!种放法．

5

如果把棋盘换成12 × 12的，而其他条件不变，结果会如何呢？读者自行思考．

图 1.2

第1章 排列、组合、二项式定理9

1.3 多重集合的排列与组合

前面考虑的集合中，都没有重复的元素，即单重集合；现在考虑多重集合，即有重复元素的集合，例如：

M = {a, a, a, b, c, c, d, d, d, d }

就是一个10元素的多重集合，其中有3个a，1个b，2个c，4个d．通常，将M表示为

M = {3⋅a, 1⋅b, 2⋅c, 4⋅d }，

一般来说，多重集合表示为M = {k1⋅a1, k2⋅a2,L, kn⋅an}，其中ai（i = 1, 2,L, n）表示元素的种类，ki（i = 1, 2,L, n）表示每类元素的个数．

1.3.1 多重集合的排列

定理1.3.1 多重集合M = {∞⋅a1,∞⋅a2,L,∞⋅ak}的r排列数为k r．证明：在构造M的一个r排列时，第1项有k种选择，第2项有k种选择，……，第r项有k种选择．由于M中的每个元素都是无限重的，所以r排列中的任一项都有k种选择，且不依赖于前面已选择的项，故M的r排列数为k r．

注意：由上面的证明易知，M中每个元素的重数至少为r．定理1.3.2 多重集合M ={ k1⋅a1, k2⋅a2,L, kn⋅an }的全排列数为(k1+k2+⋅⋅⋅+kn)!.k1!k2!⋅⋅⋅kn!证明：方法1 集合M有k1+ k2+L+ kn个元素，a1占集合M的全排列中的k1个位

k1+k2+L+kn

置，选取a1所占位置的方法数为；在确定了k1个a1的位置后，还有

k1

k2+L+kn

(k2 + k3 +L+ kn)个位置，a2占其中的k2个位置，方法数为．

k2

类似的，依次选择位置安排a3, a4 ,L, an. 由乘法原则知，M的全排列数为

k+k+⋅⋅⋅+knk2+k3+⋅⋅⋅+knkn 12 ⋅⋅⋅

kk12kn

==

(k1+k2+⋅⋅⋅+kn) !

k1!(k2+⋅⋅⋅+kn)!

×.

(k2+k3+⋅⋅⋅+kn)!k!

×⋅⋅⋅×n

k2!(k3+⋅⋅⋅+kn)!kn!

(k1+k2+⋅⋅⋅+kn) !

k1!k2!⋅⋅⋅kn!

方法2 先把M中所有的k1+ k2+…+ kn个元素看成是互不相同的，则它的全排列数为

(k2 + k3 +L+ kn) !．但这里ki个ai是相同的，所以在这(k2 + k3 +L+ kn)!个排列中，ki！个ai的位置相同且同其他元素排列也相同的排列是同一个．故知M的全排列数为

10组合理论及其应用

(k1+k2+⋅⋅⋅+kn)!

．

k1!k2!⋅⋅⋅kn!

【例15】 求1.2节例13的9人小组的进站方案数．

解：设9个人分别为a1, a2,L, a9，分隔符为“△”，则集合M={a1, a2,L, a9，5*△}的每

14 !

=726 485 760种. 个全排列对应着9人的一种进站方式，共有

1!×⋅⋅⋅×1!×5 !

【例16】 将52张牌平均分给4个人，每人有一个5张牌的同花顺的概率是多少？

解：首先分给4个人每人一个5张牌的同花顺的个数：

（1）4个人每人的5张同花顺颜色均不同．每种花色均有9种不同的同花顺．故共有P（4, 4）94种可能．

（2）4个人中有两人是同色的同花顺，另外两人是另外两种花色的．两个人是同色

4

的同花顺的分发有10种，他们的花色有4种选择．故共有P (4, 2)×10×P (3, 2)×92种.

1

43

（3）4个人中每两人是一种同花顺．同上，共有P (4, 2) ×× 10 ×× 10 × P(2, 2)

11种.

3224168

其余32张牌平均分配给4个人的分法有种．将52张牌平均

8888

52392613

分给4个人的分法有种．因而所求的概率P(n)为

13131313443P(4, 4)×94+×P(4, 2)×10×P(3, 2)×92+×P(4, 2)×10××10×P(2, 2)111P(n)=52392613×××131313133224168 ××××=0.0006 %.8888【例17】 如图1.3所示，只可以沿水平和垂直道路向右或向上走，计算从(0, 0)点到(n, n)点的不穿过直线y = x的路径数．

在解答此题之前，首先考虑两个较简单的 问题．

（1）图1.4中，从(0, 0)点开始，只可以沿水平和垂直道路向右或向上走，要走到(m, n)点，共有多少种走法？

（2）利用图1.5来说明等式

m+n+1mn+i=∑

mi=0i

图 1.3