《组合数学及其应用》教案

前言 绪论

第1章 鸽巢原理

1.1 鸽巢原理的简单形式 1.2 鸽巢原理的加强形式 1.3 Ramsey问题与Ramsey数 1.4 Ramsey数的推广 习题

第2章 基本计数问题

2.1 加法原则与乘法原则 2.2 排列与组合

2.3 多重集合的排列与组合 2.4 二项式系数

2.5 集合的分划与第二类Stirling数 2.6 正整数的分拆 2.7 分配问题 习题

第3章 容斥原理

3.1 引论 3.2 容斥原理

3.3 容斥原理的应用

3.4 Mobius反演及可重复的圆排列 习题

第4章 递推关系

4.1 递推关系的建立

4.2 常系数线性齐次递推关系的求解 4.3 常系数线性非齐次递推关系的求解 4.4 用迭代归纳法求解递推关系 4.5 Fibonacci数和Catalan数 习题

第5章 生成函数

5.1 引论

5.2 形式幂级数

5.3 生成函数的性质

5.4 用生成函数求解递推关系 5.5 生成函数在计数问题中的

5.6 有位置的排列及棋子多项式 习题

第6章 Polya计数理论

6.1 引论

6.2 置换群的基本知识 6.3 计数问题的数学模型 6.4 Burnside引理 6.5 映射的等价类 6.6 Polya 计数定理

第1章 鸽巢原理

第一节 鸽巢原理的简单形式

定理1.1.1 如果把n+1个物品放入个n盒子中,那么至少有一个盒子中有两个或更多的物品。

例1 共有12个属相，今有13人，则必有两人的属相相同。

例2 在边长为1的正方形内任 取5点，则其中至少有两点，它们之间的距离不超过22。

证明：把边长为1的正方形分成4个边长为的小正方形，在大正方形内任取5点，则此5点分别落在4个小正方形中。由鸽巢原理，至少有两点落在同一小正方形中，此两点即满足要求。

例3 给出m个整数a1,a2,,am。证明：必存在整数k，l(0klm)使得

m|(ak1ak2al)。

证明： 构造部分和序列 s1a1，

s2a1a2， ，

sma1a2am， 则有如下两种可能：

（1）存在整数h(1hm)，使得m|sh。此时，取k0,lh即满足题意。 （2）对任一整数i，均有simodm0(1im。令risi(momd，)则有

，这样，1rim1(1im)m个余数均在1到m1之间。由鸽巢原理知，存在整

数kl(1k,lm)，使得rkrl。不妨设lk，则 ak1ak2al

(a1akak1al)(a1ak) slsk

(rlrk)(modm) 0(modm)。 综合（1）（2）知，题设结论成立。

例4 一个棋手有11周时间准备锦标赛，他决定每天至少下一盘棋，一周中下棋的次数不能多于12次。证明：在此期间的连续一些天中他正好下棋21次。

例5 从1到200的所有整数中任取101个，则这101个整数中至少有一对数，其中的一个一定能被另一个整除。

第二节 鸽巢原理的加强形式

定理1.2.1 设q1,q2,qn都是正整数，如果把q1q2qnn1个物品放入n个盒

，子，那么或者第1个盒子至少包含q1个物品，或者第二个盒子至少包含q2个物品，或者第n个盒子至少包含qn个物品。

推论1.2.1 若将n(r1)1个物品放入n个盒子中，则至少有一个盒子中有r个物品。

mm2mnr1。则 推论1.2.2 设m1,m2,,mn是n个整数，而且1nm1,m2,,mn中至少有一个数不小于r。

推论1.2.3 若将m个物品放入n个盒子中，则至少有一个盒子中有不少于 mmm[]个物品。其中，[]是不小于的最小整数。 nnn

例1 设有大小两只圆盘，每个都划分成大小相等的200个小扇形，在大盘上任选100个小扇形漆成黑色，其余的100个小扇形漆成白色，而将小盘上的200个小扇形任意漆成黑色或白色。现将大小两只圆盘的中心重合，转动小盘使小盘上的每个小扇形含在大盘上的小扇形内。证明：有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色。

例2(Erds) 任意n21个实数a1,a2,a3,,an21组成的序列中，必有长为n+1的非降子序列，或必有一个长为n+1的非升子序列。

Paul Erds (1913-1996) ，匈牙利人，当代最伟大的数学家之一。他一生中同485位合作者发表过1475篇数学论文。Erds研究的领域主要是数论和组合数学，但他的论文涵盖的学科有泛函分析、代数结构、群论、拓扑学、多项式、测度论、差分方程与函数方程、Fourier分析、逼近论、统计、计算机科学、信息论等等。《Mathematical Reviews》曾把数学划分为大约六十个分支，Erds的论文涉及到了其中的40%。如此广泛的研究方向，再加上他的惊人数量的论文，超长的合作者名单，使他的触角伸展到了数学的几乎每一个角落。

例3 将1到16的16个正整数任意分成三部分,其中必有一部分中的一个元素是某两个元素之差(三个元素不一定互不相同)。

第三节 Ramsey问题和Ramsey数

1.3.1 Ramsey问题

1958年6-7月号美国《数学月刊》上登载了如下的问题：“任何6个人的聚会，其中总会有3人相互认识或3人互相不认识。”这就是著名的Ramsey问题。

分析：以6个顶点分别代表6个人，如果两人相识，则在相应的两顶点间连一红边，否则在相应的两顶点间连一蓝边则上述问题等价于下面的命题。

命题1.3.1 对6个顶点的完全图K6任意进行红、蓝两边着色，都存在一个红色三角形或一个蓝色三角形。

证明： 设v1,v2,v3,v4,v5,v6是K6的6个顶点，v1与v2,v3,v4,v5,v6所连的5条边着红色或蓝色。由鸽巢原理，其中至少有3条边同色，不妨设v1与v2,v3,v4所连的3条边均为红色，如图所示。若v2,v3,v4间有一条红边，不妨设为v2v3，则v1v2v3是一红色三角形。否则，v2,v3,v4间均为蓝边，即v2v3v4是一蓝色三角形。

v1 v4 v2 v3

命题1.3.2 对6个顶点的完全图K6任意进行红、蓝两边着色，都至少有两个同色三角形。

命题1.3.3 对10个顶点的完全图K10任意进行红、蓝两边着色，都或者有一红色K4，或者有一蓝色K3。

命题1.3.4 对9个顶点的完全图K9任意进行红、蓝两边着色，都或者有一红色K4，或者有一蓝色K3。

1.3.2 Ramsey数

对于任意给定的两个正整数a和b,如果存在最小的正整数r(a,b)，使得当Nr(a,b) 时，对KN任意进行红、蓝两边着色，KN中均有红色Ka，或蓝色Kb，则r(a,b)称为Ramsey数。

由命题1.3.1知：r(3,3)6；由命题1.3.4知r(4,3)9。从下面两图的着色方式可知：r(3,3)=6，r(4,3)=9。

目前所已知的一些Ramsey数：

b/a 2 3 4 5 6 7 8 9 2 2 3 4 5 6 7 8 9 3 3 6 9 14 18 23 28 36 4 4 9 18 25 5 5 14 25 6 6 18 7 7 23 8 8 28

9 9 36

定理1.3.1 对任意的正整数a3,b3，有

r(a,b)r(a1,b)r(a,b1)。

定理1.3.2 对任意的正整数a2,b2，有

ab2r(a,b)。

a1

本章小结：

鸽巢原理也叫做狄利克雷（P.G.Drichlet）原理。如此简单明了的事实，竟冠以著名德国数学家的名字，似乎有点“过分”，但正如我们上面所看到的，这样一个貌不惊人的几乎是不证自明的原理，却有着这么多的出乎意料的应用。而这些应用的关键就在于“鸽巢”的构筑，这也是鸽巢原理运用的难点所在。因此，要想熟练地掌握这一原理，还需同学们多加练习。

第2章 基本计数问题

第一节 加法原理与乘法原理

2.1.1 加法原则

设事件A有m种选取方式，事件B有n种选取方式，则事件A或B有m+n种选取方式。

定理2.1.1 设A，B为有限集，A1,A2,,An满足AiAj(1ijn) 则AiAi

i1i1nn

例1 在所有六位二进制数中，至少有连续4位是1的有多少个？

2.1.2 乘法原则

设事件A有m种选取方式，事件B有n种选取方式，则事件A以后再选取事件B有mn种选取方式。

定理2.1.1 设A，B为有限集，Am,Bn，则ABABmn。

推论2.1.1 设A1,A2,,An为n个有限集合，则

A1A2AnA1A2An。

例2 从5位先生、6位女士、2位男孩和4位女孩中选取1位先生、1位女士、1位男孩和1位女孩，共有5×6×2×4=240种方式（由乘法原理）。而从中选取一个人的方式共有5+6+2+4=17种方式（由加法原理）。

例3 在1000到9999之间有多少个各位数字不同的奇数？

第二节 排列与组合

2.2.1 集合的排列

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

定理2.2.1 设对于满足rn的正整数n和r，有

n!。 P(n,r)n(n1)(nr1)(nr)!

例1 从将a，b，c，d，e，f进行排列。问： （1）使得字母b正好在字母e的左邻的排列有多少种？ （2）使得字母b在字母e的左边的排列有多少种？

例2 从{1，2，„，9}中选出不同的7个数字组成7位数，要求5和6不相邻，问有多少种方法？

1n!定理2.2.2 n元集合的r圆排列数为P(n,r)。

rr(nr)!

例3 10个男生和5个女生聚餐，围坐在圆桌旁，任意两个女生不相邻的坐法有多少种？

2.2.2 集合的组合

n元集合S的一个r组合是指先从S中选出r个元素的一种无序选择，其组合数记为r。 CnnP(n,r)n!r定理2.2.3 若0rn，则Cn。 r!r!(nr)!r

例4 从1，2，„，100中选出两个不同的数，使其和为偶数，问有多少种取法？

例5 在一个凸n(n4)边形C的内部，如果没有3条对角线共点，求其全部对角线在C的内部的交点的个数。

解：从右图可看出，对角线在C的内部的交点与凸n边形的四个顶点

n1成一一对应关系，故交点的个数为n(n1)(n2)(n3)。

424

nn推论2.2.1 若0rn，则。

rnr

nnnnn定理2.2.4 若对任意正整数n，有2。

012n

例6 从求至少出现一个6且能被3整除的五位数的个数。

例7 从某车站有6个入口，每个入口每次只能进一个人，问9人小组共有多少种进站方案？

解： 第1个可以有6种进站方式，即可从6个入口中的任一个进站；第2个人也可以选择6个入口中的任一个进站，但当他选择与第1人相同的入口进站时，有在第1人前面还是后面两种方式，所以第2个人有7种进站方案；同理，第3个人有8种进站方案，„，第9人有14种进站方案。由乘法原理，总的进站方案数为67147285760。

第三节 多重集合的排列与组合

2.3.1 多重集合的排列

我们通常所讨论的集合要求集合的各个元素互不相同，如果我们允许集合的元素可以相同，则这样的集合我们称为多重集合。

一般地，多重集合可表示为

M{k1a1,k2a2,,knan}

其中，a1,a2,,an为M中所有的互不相同的元素，M中有ki个ai(1in)，称 ki为ai的重数。ki是正整数，也可以是，表示M中有无限个ai。

定理2.3.1 多重集合

M{k1a1,k2a2,,knan} 的r排列数为kr。

例1 用26个英文字母可以构造出多少个包含4个元音字母、长度为8的字符串？

定理2.3.2 多重集合

M{k1a1,k2a2,,knan}

(kkkn)!的全排列数为12。

k1!k2!kn!

例2 求2.2节例7中9人小组的进站方案。

解：设9个人分别为a1,a2,,a9，分界符为“∆”，则集合

M{a1,a2,,a9,5}的每个全排列对应着9人的一种进站方案，总的方案种数为

14!7285760。

1!1!5!

例3 下图中，从(0，0)点沿水平和垂直道路可走到(m,n)点，问有多少种走法？

(m,n) mn解： 每条路径对应着多重集合M{mx,ny}的一个全排列，即一共有种

m不同的走法。

例4 将6个蓝球，5个红球，4个白球，3个黄球排成一行，要求黄球不挨着，问有多少种排列方式？

(0,0) 2.3.2 多重集合的组合

多重集合M的r组合是指从M中无序地选取r个元素。

定理2.3.3 多重集合

M{a1,a2,,an} 的r组合数为Ckrr1。

例5 从M{1,2,,n}中能够取出多少个长为r的递增序列a1,a2,,ar，使得

ai1ais1(s0;i1,2,,r1)。

定理2.3.4 多重集合 M{a1,a2,,ak}

1要求a1,a2,,ak}至少出现一次的r组合数为Crk1。

定义2.3.1 设集合X{x1,x2,,xm}是一个全序集，x1x2xm，那么由 X中的n个字母构成的字符串xi,xi,,xi，只要xixixi，就称其为X

12n12n上长度为n的增字。

定理2.3.5 设集合X{x1,x2,,xm}是一个全序集，则X上长度为n的增字共有

nCmn11个。

第四节 二项式系数

2.4.1 二项式定理

定理2.4.1(二项式定理) 设n为一正整数，则对任意的x和y，有

122n2n1n1(xy)nynCnxyn1CnxyCnxyxn

rrnrCnxy。 r0n

定理2.4.2(牛顿二项式定理) 对一切实数和x(x1)，有

r(1)(r1)r(1x)xxr!r0rr0

2.4.2 二项式系数的基本性质

n

nn（1）对称关系。

rnr（2）递推关系 nn1n1(nr1)。 rrr1（3）单峰性 （略）

2.4.3 组合恒等式

nnn等式1：2n。

01nnnnnnn等式2：。

024135nnn等式3：12nn2n1。

12n01nn1等式4：。

kkkk12nn2n等式5：。

k0knmnmn等式6：。

i0irimr

2.4.3 多项式定理

定理2.4.3(多项式定理) 设n为正整数，则

nn1n2nt(x1x2xt)nxxx12t

n1n2ntmnn!其中 nnnn!n!n!t1212t称为多项式系数；而其中的求和号是对所有满足

n1n2ntn

的非负整数序列n1,n2,,nt求和。

3例1 展开(x1x2x3x4x5)7，则x12x3x4x5的系数为

7!420。

2!0!1!3!1!

3例2 展开(2x13x25x3)6，则x12x3x4x5的系数为 6!23(3)5236000。 3!1!2!

注： 在多项式定理中，其右端的求和号中所包含的项数就是方程

n1n2ntn

n的非负整数解的数目，即Cnt1项。

第五节 集合的分划与第二类Stirling数

定义2.5.1 设A1,A2,,Ak是A的k个子集，若它们满足：

(1)Ai(1ik)；

(2)AiAj(1ijk)； (3)AA1A2Ak。

则称{A1,A2,,Ak}是A的一个k分划，并记为

AA1A2Ak

称Ai(1ik)为A的上述k分划的一个块。

定义2.5.2 一个n元集合的全部k分划的个数叫做第二类Stirling数，记作S(n,k)。

定理2.5.1 第二类Stirling数S(n,k)满足递推关系 S(n1,k)S(n,k1)kS(n,k)(1kn)。

证明：S(n1,k)是集合A{a1,a2,...,an,an1}的k分划的个数，这些k分划可以分为两类：

第(1)类：{an1}是A的k 分划中的一个块。这时，只需对集合A{an1}进行m-1分划，再加上{an1}这一块，就构成了A的k分划。这类分划有S(n,k1)个。

第(2)类：{an1}不是A的k分划中单独的一块。此时，先构造A{an1}的k分划，共有S(n,k)种方法。然后，对于A{an1}的每个k分划，将an1加到该k分划的k个块中的某一块，从而构成A的k分划。因此，由乘法原理，集合A的此类k分划共有kS(n,k)个。

综上所述知原命题成立。

定理2.5.2 第二类Stirling数S(n,k)满足下列性质： （1）S(n,2)2n11；

2（2）S(n,n1)Cn； （3）S(n,1)1;S(n,n)1;S(n,k)0(kn)。

定理2.5.3 第二类Stirling数S(n,k)满足递推关系 S(n1,k)S(n,k1)kS(n,k)(1kn)。 注：令

xnx(x1)(x2)(xn1)，

若

xnS1(n,k)xk，

k0n则称S1(n,k)为第一类Stirling数。换句话说，S1(n,k)就是多项式xn中的xk系数。显然，当nk时，S1(n,k)0。

例： x4x(x1)(x2)(x3)x46x311x26x。由定义，有

S1(4,0)0,S1(4,1)6,S1(4,2)11,S1(4,3)6,S1(4,4)1。

定理： 第一类Stirling数满足如下递推关系： S1(n1,k)S1(n,k1)nS1(n,k)(n0,k0) S1(0,0)1,S1(n,0)0(n0)

注： 第二类Stirling数也可以由下式定义：

xS(n,k)[x]k。

nk0n

第六节 正整数的分拆

定义2.6.1 正整数n的一个k分拆是把n表示成k个正整数的和

nn1n2nk(k1)

的一种表示法，其中

ni0(1ik)

ni称为该分拆的分部量。如果表达式是无序的，即对诸ni任意换位后的表示法都只视为一种表示法，这样的分拆称为无序分拆，或简称为分拆。反之，若表达式是有

序的，即表达式右边的和不仅与各项的数值有关，而且与各项的次序有关，不同的次序认为是不同的表示法，这样的分拆称为有序分拆。

2.6.1 有序分拆

k1定理2.6.1 正整数n的有序k分拆的个数为Cn1。

证明：正整数n分成k个分部量的一个有序分拆 nn1n2nk 等价于方程

x1x2xkn

的正整数解(n1,n2,,nk)。由定理2.3.4即得结论。

注： 由定理2.3.4和定理2.6.1知，正整数n的有序k分拆数等于多重集合

k1M{a1,a2,,ak}的a1,a2,,ak至少出现一次的n组合数均为Cn1。

定理2.6.2 （1）正整数n的有序k分拆，要求第i个分部量大于等于pi，其个数为

knkp1i。

i1k1k1（2）正整数2n分拆成k个分部，各分部量都是正偶数的有序分拆个数为Cn1。

（3）正整数n分拆成k个分部，若n与k同为奇数或同为偶数，则n的各分部量都是奇

nk1数的有序分拆数为2。

k1

2.6.2 无序分拆

k1定理2.6.1 正整数n的有序k分拆的个数为Cn1。

证明：正整数n分成k个分部量的一个有序分拆 nn1n2nk 等价于方程

x1x2xkn

的正整数解(n1,n2,,nk)。由定理2.3.4即得结论。

用B(n,k)表示n的k分拆的个数，用B(n)表示n的所有分拆的个数。显然 （1）B(n,k)0(kn)； （2）B(n)B(n,k)。

k1n

定理2.6.1 n的k分拆数B(n,k)满足递推关系 B(nk,k)B(n,1)B(n,2)B(n,k) 及B(n,1)1,B(n,n)1。

例1 正整数n的2分拆数为

nB(n,2)

2nn其中，表示小于等于的最大正数。

22

定理： 周长为2n，边长为整数的三角形的个数等于n的3分拆数。

证明： 设n的一个3分拆为nxyz，则 2(xyz)(xy)(xz)(yz)2n， 其中，(xy)(xz)2x(yz)yz，

同理，(xy)(yz)xz，(xz)(yz)xy。 因此xy,xz,yz可组成一个三角形，且周长为2n。

反之，设一个三角形的周长为2n，其三条边长a,b,c是整数，则

abcn，

2设xna,ynb,znc，显然x,y,z都是正整数，而 xyznanbnc3n(abc)n， 所以xyz是n的一个3分拆。证毕。

2.6.3 分拆的Ferrers图

设n的一个k分拆为

nn1n2nk(n1n2nk)(2.6.8)

在一条水平直线上画n1个点，在其下面一条直线上画n2个点，且使这两条直线上的第一个点在同一条竖线上，其他点依次与上一行的点对齐；依次类推，最后在第k条直线上画nk个点，第一个点与前面各行的第一个点均在同一条竖线上，其他点依次与上面各行的点对齐。这样得到的点阵图称为n的k分拆（2.6.8）的Ferrers

图。

例 15的4分拆15=5+5+3+2的Ferrers图为 

   反过来，对于n的一个Ferrers图，又可按照上述规则对应于n的唯一的一个分拆。所以，n的分拆同它的Ferrers图之间是一一对应的。

把一个Ferrers图的各行改成列，但其相对位置不变，这样又得到一个Ferrers图，称为原Ferrers图的共轭图。

如前述例子中的15的4分拆的Ferrers图的共轭图为



   

定理2.6.4 正整数n的k分拆的个数等于n的最大分部量为k的分拆数。

定理2.6.5 正整数n的自共轭分拆的个数等于n的各分部量都是奇数且两两不等的的分拆的个数。

定理2.6.6 正整数n的分部量两两不等的分拆的个数等于n的各分部量都是奇数的分拆的个数。

第七节 分配问题

分配问题的叙述是：把n个球放到r个盒子里，共有多少种不同方案？ 本问题的解答须考虑三个方面的因素： 1、n个球是完全相同的还是完全不同的； 2、n个盒子是完全相同的还是完全不同的； 3、是否允许有空盒。

n个球 不 同 不 同 不 同 不 同 相 同 相 同 相 同 相 同 分配方案数表 r个盒子 允许空盒? 不 同 允 许 不 同 不允许 相 同 相 同 不 同 不 同 相 同 相 同 允 许 不允许 允 许 不允许 r分配方案数 rn r!S(n,r) S(n,i)i1rS(n,r) nCnr1 r1Cn1 允 许 不允许 B(n,i)i1B(n,r)

例1 桥牌时，52张牌分发给4个人，每人13张，问每人有一张A的概率是多少？

解： 每人有一张A的概率是 (13!)448!4!10.55%。 4(12!)52!

例2 (xyz)4的展开式有多少项？

431解： 共有N15项。分别为

4x4,x3y,x3z,x2yz,x2y2,x2z2,xy3,xz3,xyz2,xy2z,y2z2,y3z,z3y,y4,z4。

例3 会议室中有2n+1个座位，现排成3排，要求任何两排的座位都要占大多数。问有多少种排法。

例4 把4个相同的橘子和6个不同的苹果放到5个不同的盒子里，问每个盒子里有2个水果的概率有多大？

本章小结：

从上面所学内容，我们可以看到，计数问题最本质的处理方法就是配对与分组。分组不难理解，而所谓配对法就是若想计算某集合A的元素个数A，其关键是寻找一个既能与A建立一一对应又便于计数的集合B。因此，配对法实质上是一种转换

法，它把求A的问题转化为求B的问题。至于寻找合适的集合B，往往需要相当的技巧。

第3章 容斥原理

第一节 引论

在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。 先考虑下面几个简单的问题。

例1 求1到600间不能被6整除的整数的个数。

例2 求{1,2,,n}的1不在第一个位置上的全排列的个数。

例3 求不超过20的正整数中，是2的倍数或是3的倍数的数的个数。

第二节 容斥原理

定理3.2.1 设S是有限集合，P1,P2,,Pm是同集合S有关的m个性质，设Ai是S中具有性质Pi的元素构成的集合(1im),Ai是S中不具有性质Pi的元素构成的集合

(1im)，则S中不具性质P1,P2,,Pm的元素的个数为

A1A2AmSAii1m{1,2,...,m}的2组合AiAj{1,2,...,m}的3组合AiAjAk

(1)mA1A2Am。

推论3.2.1 设S是有限集合，P1,P2,,Pm是同集合S有关的m个性质，设Ai是S中具有性质Pi的元素构成的集合(1im), 则S中至少具有一个性质Pi的元素的个数为

A1A2AmAii1m{1,2,...,m}的2组合AiAj{1,2,...,m}的3组合AiAjAk

(1)m1A1A2Am

证明一：（数学归纳法）

当n2 时，要证明：|A1A2||A1||A2||A1A2|

这可由A1A2等于不相交的两个集合A1和A2\\(A1A2)的并推出， 而A2等于不相交的两个集合A2\\(A1A2)和A1A2的并。 所以，|A1A2||A1||A2\\(A1A2)| ①

|A2||A2\\(A1A2)||A1A2| ②

由①、②知|A1A2||A1||A2||A1A2| 假设对n1个集合，要证的等式成立； 对n个集合时，有

| |nn1n1n1||AAiii1n1i1i1An||Ai|i1n1i1|An||(Aii1 n)A|A||Ain||(AiAn)|

I{1,2,,n1}I(1)|I|1|Ai||An|iII{1,2,,n1}I(1)|I|1|(AiAn)|

iI 将和式中具有相同因子数的项合并，即可得到要证明的等式。

证法二：（贡献法）

如果xAi，则xAi(i1,2,,n)，公式两端均为0，成立；

如果xAi，设x恰属于m个Ai，1mn。此时，公式右端中Ai对x共

i1i1ni1nn1计数Cm次，

1ijn2AiAj对x共计数Cm次，

1ijkn3AiAjAk对x共计数Cm次，„..，

1i1iMnm|Ai1Aim|对x共计数Cm次，并且在此后的各项中，x均未

123m被计数，故公式右端对x共计数Cm CmCm(1)m1Cm00123mCm(CmCmCmCm(1)mCm)1(11)m1

故等式成立。

例1 1与1000之间不能被5，6，8整除的整数有多少个？

例2 展求由a,b,c,d四个字符构成的n位字符串中，a,b,c,d至少出现一次的字符串的数目。

例3 在欧拉函数(n)表示小于n且与n互素的整数的个数。求(n)。

解： 将n分解成素因子的乘积形式：

ii2np1i1p2...pqq 则有

(n)n(1111)(1)(1)。 p1p2pq

例4 若图G有n个顶点，且不含有完全k子图(k2)，则它的顶点的次数d(x)满足不等式

(k2)n mind(x)xXk1

问题： 设S是一有限集合，P{P1,P2,,Pm}是S上的性质集合。求集合S中恰好具有P中r个性质的元素个数N(r)(1rm)。

S中具有性质P用N(Pi1,Pi2,,Pik)表示i1,Pi2,,Pik的元素个数，规定w(0)S，令

w(k)1i1i2...ikmN(Pi1,Pi2,,Pik)。

r定理3.2.2 设集合S中具有性质集合P{P1,P2,,Pm}中恰好个性质的元素的个数为N(r)，则

r1r2mrmN(r)w(r)w(1)w(2)(1)w(m)。

rrr

例5 某学校有12位教师，已知教数学课的教师有8位，教物理课的教师有6位，教化学课的教师有5位。其中，有5位教师既教数学又教物理，有4位教师既教数学又教化学，兼教物理和化学的有3位教师，还有3位教师兼教这三门课。试问： （1）教数、理、化以外的课的教师有几位？ （2）只教数、理、化中一门课的教师有几位？ （3）正好教数、理、化中两门课的教师有几位？

第三节 容斥原理的应用

3.3.1 具有有限重复数的多重集合的r组合数

例1 求S{3a,4b,5c}的10组合数。

3.3.2 错排问题

错排问题的提法：

集合{1,2,,n}的一个错排是该集合的一个满足条件

ijj(1jn)

的全排列i1i2in，即集合{1,2,,n}的一个没有一个数字在它的自然顺序位置上的全排列。试求的全部错排个数Dn。

定理3.3.1 对任意正整数n，有

1111Dnn!(1(1)n)。

1!2!3!n!

证明： 记S为a1,a2,,an 的所有排列的集合，Sk是S中所有满足ak在第k号位置上的排列的集合，k1,2,,n。

显然|S|n!，|Si|(n1)!，SiSj|(n2)!，„„，

|S1Sn|1

所以，|S1Sn||S||S1Sn|

12 n![Cn(n1)!Cn(n2)!(1)n1]

n![1

111(1)n](n2) 1!2!n!

3.3.3 有禁止模式的排列问题

问题：

设某班有8位学生排成一队出去散步，第二天再列队时，同学们都不希望他前面的同学与前一天相同，问有多少种排法？

将上述例子推广并进行抽象，得问题的提法：

n,}用Qn表示{1,2,的不出现12,23,„,(n1)n这些模式的全排列的个数(规定

Q11)，求Qn。

定理3.3.2 设对任意正整数n,有

n1n1n1n1QNn!(n1)!(n2)!(1)1! 12n1

例2 多重集合M{4x,3y,2z}的全排列中不出现xxxx,yyy,zz模式的排列有多少种？

例3(menage问题) n对夫妇参加宴会围桌就座，要求男女相间并且每对夫妇两人不得相邻，问有多少种就座方式？

解 利用容斥原理，可求得就座方式总数为

n2n2nkUn(1)k(nk)!。

2nkkk0

第四节 Mobius反演及可重复圆排列

Mobius函数：

对任意自然数n，若n1，则n可唯一分解为素数幂的乘积

l1l2np1p2prlr,(3.4.1)

其中，p1,p2pr是不同的素数，li1(1ir)。定义Mobius函数(n)为

1若n1；(n)0若(3.4.1)中某li1；

(1)r若(3.4.1)中l1=l2lr1。

引理3.4.1 对任意正整数n，有

1(d)d|n0(若n1)；(若n1)。

证明: 当n=1时, 定理显然成立. 若n1, 设

aka2np1a1p2pk, n1p1p2pk。

(d)(d)

d|nd|n1(1)1ik(p)i(pipj)...(p1pk)

1ijkkkkk(1)0。 01k

定理3.4.1（Mobius反演定理） 设f(n)和g(n)是定义在自然数集N上的两个函数，若对任意正整数n，有

nf(n)g(d)g()

dd|nd|n则可将g表示为f的函数：

ng(n)(d)f()。

dd|n

例1 欧拉函数(n)满足

(n)nd|n(d)d,

并由Mobius反演定理可得

nn(d)()

dd|nd|n

例2（可重圆排列问题） 求集合S{1,2,,m}的n可重圆排列数。

n1d解：T(n)(d)m。

nd|n

本章小结：

本章介绍了容斥原理的基本定理，共三条。利用这些基本定理，我们解决了错排问题，有禁止模式的排列问题等问题，并讨论了Mobius反演问题。这些都是组合数学中重要且经典的问题。

容斥原理应用的要点在于对所考虑计数的集合中的元素进行恰当的分组，同时必须使得这些分组所产生的子集合，任意两个、三个、„、n个子集合的交都能容易地计数。要想熟练地利用容斥原理解决问题，还需同学们多思考、多作练习。

第4章 递推关系

第一节 递推关系建立

定义4.1.1 给定一个数的序列H(0),H(1),,H(n),，若存在整数 ,使当nn0时，可以用等号（或大于号,小于号）将H(n)与其前面的某些项H(i)(0in)联系起来，这样的式子就叫做递推关系。

例1（Hanoi 塔问题） 现有A，B，C三根立柱以及n个大小不等的中空圆盘，这些圆盘自小到大套在A柱上形成塔形，如下图所示。要把n个圆盘从A柱上搬到C柱上，并保持原来的顺序不变，要求每次只能从一根立柱上拿下一个圆盘放在另一个立柱上，且不允许大盘压在小盘上。问至少要搬多少次？

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在

一个庙里留下了三根金刚石的棒，第一根上面套着个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去， 庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己 运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。后来，这个传说就演变为汉诺塔游戏。

例2 在信道上传输由a,b,c三个字母组成的长为n的字符串，若字符串中有两个a连续出现，则信道就不能传输，令表示信道可以传输的长为n的字符串的个数，求满足的递推关系。

解：信道上能够传输的长为n(n2)的字符串可分成如下四类： （1）最左边字符为b； （2）最左边字符为c；

（3）最左边两个字符为ab； （4）最左边两个字符为ac

如图所示，前两类字符串分别为f(n1)个，后两类字符串有f(n2)个。

b

 c

 a

b c  a 

易求得f(1)3，f(2)8，从而得 f(n)2f(n1)2f(n2)(n3), f(1)3,f(2)8.

例3 考虑0，1字符串中“010”子串的相继出现问题，例如，在110101010101中，我们说“010”在第5位和第9位出现，而不是在第7位和第11位出现，在整个字符串中“010”共出现两次，计算n位0，1字符串中“010”子串在第n位出现的字符串有多少？

解：设n位0，1字符串中“010” 子串在第n位出现的字符串的个数为f(n)，则有

f(n)2n3f(n2)(n5) f(3)1,f(4)2

例4 设P平面上n个连通区域的公共交界点，如右图所示。现用k种颜色对其着色，要求有公共边界的相邻区域着以不同的颜色。令表示不同的着色方案数，求它所满足的递推关系。

例5 设X是一具有乘法运算的代数系统，乘法不满足结合律，用xy表示x对y之积。如果

x1,x2,,xnX

而且这n个元素依上面列出的顺序所能作出的一切可能的积彼此不同，其个数记为

f(n)，求f(n)满足的递推关系。

第二节 常系数线性齐次递推关系的求解

定义4.2.1 设k是给定的正整数，若数列f(0),f(1),f(n), 的相邻k+1项间满足关系

f(n)c(n)f(n1)c(n)f(n2)

c(n)f(nk)g(n),(4.2.1)对nk成立，其中ck(n)0，则称该关系为{f(n)}的k阶线性递推关系。如果

c1(n),c2(n),,ck(n)都是常数，则称之为k阶常系数线性递推关系。如果g(n)0，则称之为齐次的。

如果有一个数列代入递推关系（4.2.1），使得其对任何n，k都成立，则称这个数列是递推关系（4.2.1）的解。

常系数线性齐次递推关系的一般形式为：

f(n)c1f(n1)c2f(n2)ckf(nk)定义4.2.2 方程

(nk,ck0),(4.2.2)

xkc1xk1c2xk2ck0(4.2.3)

叫做递推关系（4.2.2）的特征方程。它的k个根q1,q2,,qk（可能有重根）叫做该递推关系的特征根，其中qi,i1,2,,k是复数。

引理4.2.1 设q是非零复数，则f(n)qn是递推关系（4.2.2）的解，当且仅当q是它的特征根。

引理4.2.2 如果h1(n),h2(n)都是递推关系（4.2.2）的解，b1,b2是常数，则

b1h1(n)b2h2(n)也是递推关系（4.2.2）的解。

定义 4.2.3 如果对于递推关系（4.2.2）的每个解h(n)，都可以选择一组常数

c1,c2,,ck， 使得

nnh(n)c1q1nc2q2ckqk

nn成立，则称b1q1b2qn1,b2,bk 2bkqk是递推关系（4.2.2）的通解，其中，b为任意常数。

定理 4.2.1 设q1,q2,,qk是递推关系（4.2.2）的k个互不相等的特征根，则

nn f(n)b1q1nb2q2bkqk是递推关系（4.2.2）的通解。

例1 求解4.1节例2的递推关系

f(n)1f(n1)2f(n2), f(1)3,f(2)8.

例2 核反应堆中有和两种粒子，每秒钟内一个粒子可反应产生三个粒

子，而一个粒子又可反应产生一个粒子和两个粒子。若在时刻t0 时反应堆中只有一个粒子，问t100秒时反应堆中将有多少个粒子？多少个

粒子？共有多少个粒子？

例3 求递推关系

f(n)4f(n1)4f(n2), f(0)1,f(1)3.

定理 4.2.2 设q1,q2,,qk是递推关系（4.2.2）的全部不同的特征根，其重数分别为e1,e2,,et(e1e2etk)，那么递推关系（4.2.2）通解为

f(n)f1(n)f2(n)ft(n),

其中f(n)(bi1bi2nbieinei1)qin(1it)。

例4 求解递推关系

f(n)f(n1)3f(n2)f(n3)2f(n4), f(0)1,f(1)0,f(2)1,f(3)2.

解：原递推关系的解为

f(n)2n2n1n。

第三节 常系数线性非齐次递推关系的求解

k阶常系数线性非齐次递推关系的一般形式为

fnc1f(n1)c2f(n2)ckf(nk)g(n)(nk),(4.3.1)

其中，c1,c2,,ck为常数，ck0,g(n)0。递推关系（4.3.1）对应的齐次递推关系为

f(n)c1f(n1)c2f(n2)ckf(nk),(4.3.2)。

定理 4.3.1 k阶常系数线性非齐次递推关系（4.3.1）的通解是递推关系（4.3.1）的特解加上其相应的齐次递推关系（4.3.2）的通解。

下表对于几种g(n)给出了递推关系（4.3.1）的特解的一般形式。

g(n) 特征多项式f(n) P()0 f(n) n ns 特解an的一般形式 是P(x)0的m重根 P(1)0 1是P(x)0的m重根 P()0 anmn bsnsbs1ns1b1sb0 nm(bsnsbs1ns1b1sb0) nns n(bsnsbs1ns1b1sb0) nmn(bsnsbs1ns1b1sb0) 是P(x)0的m重根

例1 求解递推关系 f(n)2f(n1)4n1, f(0)1.

例2 求和1424n4。

例3 求解递推关系

f(n)4f(n1)4f(n2)n2n, f(0)0,f(1)1.

例4 求解Hanoi塔问题满足的递推关系

f(n)2f(n1)1,。 f(0)0

第四节 用迭代归纳法求解递推关系

迭代归纳法也是求解递推关系的一种方法，尤其对于某些非线性的递推关系，不存在求解的公式，不妨用这种方法来试一试。

例1 求解递推关系 f(n)f(n1)n3, f(0)0

迭代法并不仅仅局限于如例子1所示的直接导出的表达式。利用迭代法，还可以先将原递推关系化简，然后再求解。

（1）将非齐次递推关系齐次化

例2 求解递推关系 f(n)2f(n1)4n1, (4.4.1)f(1)3.

（2）将变系数的一般线性递推关系化为常系数线性递推关系

例3 求解递推关系

n1f(n)f(n1)1, 2nf(0)1.

（3）将一阶高次递推关系通过变量代换化为一阶线性递推关系。

应用：估计快速排序算法的平均复杂度

第五节 Fibonacci 数和Catalan数

简述

Fibonacci数列和Catalan数列是递推关系的典型问题，它们经常出现在组合计数问题中，而这两个数列本身的应用也十分广泛。

4.5.1 Fibonacci数

Fibonacci 数的来源—问题

关于Fibonacci数列的问题是一个古老的数学问题，它是由意大利著名学家Fibonacci于1202年提出来的。

问题：把一对雌雄兔子放到围栏中，每个月这对兔子都生出一对新兔子，其中雌雄各一只。从第二个月开始，每对新兔子每个月也生出一对新兔子，也是雌雄各一只。问一年后围栏中由多少对兔子？

根据分析，令f(n)表示第n个月开始围栏中兔子对数，有f(1)1,f(2)2，则有

f(n)f(n1)f(n2)(n3),(4.5.1) f(1)1,f(2)2.这是一个带有初值的递推关系，如果规定f(0)1， 则递推关系（4.5.1）就变成 f(n)f(n1)f(n2)(n2), (4.5.2)f(0)1,f(1)2.满足递推关系（4.5.2）的数列就叫做Fibonacci数列，它的项就叫做Fibonacci数。

与费波纳奇数列有关的数字现象很多：两个连续的费波纳奇数字没有公约数；数列中任何10个数之和，均可被11整除等。无论是从宏观的宇宙空间到微观的分子原子，从时间到空间，从大自然到人类社会，政治、经济、军事„„等等，人们都能找到费波纳奇数的踪迹。在期货股票市场的分析中，费波纳奇数字频频出现。例如在波浪理论中，一段牛市上升行情可以用1个上升浪来表示，也可以用5个低一个层次的小浪来表示，还可继续细分为21个或个小浪；而一段熊市行情可以用1个下降浪来表示，也可以用3个低一个层次的小浪来表示，还可以继续细分为13个或55个小浪；而一个完整的牛熊市场循环，可以用一上一下2个浪来表示，也可以用8个低一个层次的8浪来表示，还可以继续细分为34个或144个小浪。

Fibonacci数的性质

（1）Fibonacci数f(n)可以表示为二项式系数之和，即

nn1nknf(n),k. 201k（2）f(0)f(1)f(n)f(n2)1. （3）f(0)f(2)f(2n)f(2n1). （4）f(1)f(3)f(2n1)f(2n)1.

（5）f2(0)f2(1)f2(n)f(n)f(n1).

（6）f(nm)f(m1)f(n1)f(m1)f(n)(m2).

自然界中到处可見Fibonacci数列的踪迹。树技上的分枝数，多数花的瓣数都是费氏数：火鹤 1、百合3，梅花5，桔梗常为8，金盏花13，„等等。费氏数列也出现在松果上。一片片的鱗片在整粒松果上顺着两组螺线排列：一组呈顺时针旋转，另一组呈反时针，顺时针螺线的排列数目是8，反时针方向则为13，而另一组常出现的数字是“5 及 8”。向日葵也是一样，常見的螺线数目为“34 及 55”，较大的向日葵的螺线数目则为“ 及 144”，更大的甚至还有“144 及 233”。这些全都是费氏数列中相邻两项的数值。

例1 用多米诺牌（可以看作一个2×1大小的长方块）完全覆盖一个n×2的棋盘，覆盖的方案等于Fibonacci数。

例2 一个小孩上楼梯，每次可上一阶或两阶，问上n阶楼梯有多少种不同的方法？ h(n)h(n1)h(n2)(n3) h(1)1,h(2)2.

4.5.2 Catalan数

Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。

问题：在一个凸n边形中，通过插入内部不相交的对角线将其分成一些三角形区域，问由多少种不同的分法？

令h(n)表示分一个n1条边的凸多边形为三角形的方法数，并规定h(1)1。 利用递推方法，我们得到h(n)的递推关系如下：

h(n)h(k)h(nk)

k1n1这个递推关系若直接求解，将是非常困难的，但利用后面将学习的生成函数，可以较容易的2求得

12n2hn。

nn1我们称hn为Catalans数。

16例如对五边形，有h45。五种划分方案如下图。

43

例 证明有n个叶子的完全二叉树的个数为Catalan数h(n)。

例 证明从(0,0)点到(n,n)点的除端点外不接触直线yx的路径为2h(n),其中h(n)为Catalan数。

本章小结：

Fibonacci数是一个非常神奇且具有众多有趣性质的数列，问世几百年来，一直吸引着各国的研究者，至今方兴未艾。可以说，世界上没有哪一个数学问题的研究

象Fibonacci数这样获得数学家们的广泛参与和持续关注，其成果可以说是汗牛充栋。在美国，甚至专门有一本杂志刊载这方面的研究。至于Catalan数，也是组合数学里一个重要的研究对象，我们已经看到，许多计算机科学中的问题都与Catalan有关。值得一提的是，我国清代数学家明安图在其《割圜密率捷法》一书中最先应用了Catalan数，取得优秀的研究成果 。

第5章 生成函数

第一节 引论

问题导入： 投掷一次骰子，出现点数1,2,3,4,5,6的概率均为1/6. 问:连续投掷2次，出现点数和为10的概率为多少？ 问:连续投掷10次，出现的点数之和为30的概率为多少？

我们用xx2x3x5x6表示投掷一次可能出现点数1，2，3，4，5，6，观察

(xx2x3x5x6)(xx2x3x5x6)

从两个括号中分别取出xm和xn，使得xmxnx10即为两次投掷分别出现点数m,n，且mn10。由此得出，展开式中x的10次方的系数就是满足条件的方法数。

第二节 形式幂级数

定义5.2.1 设A(x)=akx与B(x)bkxk是Ｒ上的两个形式幂级数，若对任意

kk0k0k0，有akbk，则称A(x)与B(x)相等，记作A(x)B(x)。

kk定义5.2.2 设为任意实数，A(x)akxR[[x]]，则将A(x)(ak)x

k0k0称为与A(x)的数乘积。

定义5.2.3 设A(x)akx与B(x)bkxk是Ｒ上的两个形式幂函数，将A(x)与

kk0k0B(x)相加定义为 ,A(x)B(x)(akbk)xk，并称A(x)B(x)为A(x)与B(x)的和，

k0把运算“＋”叫做加法。 将A(x)与B(x)相乘定义为

A(x)B(x)(akb0ak1b1a0bk)xk

k0并称A(x)B(x)为A(x)和B(x)的积，将运算“”叫作乘法。

定理5.2.1 集合R[[x]]在上述加法和乘法运算下构成一个整环。

定理5.2.2 对于R[[x]]中的任意一个元素

A(x)akkx

k0A(x)有乘法逆元当且仅当a00。

定义5.2.4 对于任意A(x)akk1kxR[[x]]，规定DA(x)kakx, k0k0为A(x)的形式导数。

A(x)的ｎ次形式导数可以递归地定义为：

D0A(x)A(x)DｎA(x)D(Dn1A(x)) 形式导数满足如下规则：

(1)D(A(x)B(x))DA(x)DB(x)； (2)D(A(x)B(x))A(x)DB(x)B(x)DA(x)；

(3)D(An(x))nAn1(x)DA(x)。

第三节 形式幂函数

性质1 若

b0(kl)kakl(kl)

则B(x)xlA(x)。

性质2 若ba1l1kkl，则B(x)xl(A(x)akxk)。

k0

k性质3 若bx)A(x)kai，则B(i01x。

k性质4 若bA(1)xA(x)kai，则B(x)。这里，i01xai是收敛的。

i0

性质5 若bkkak，则B(x)xA(x)。

称DA(x)

性质6 若bk

性质7 若ckakbk，则C(x)ckxkA(x)B(x)。

k0ak1x，则B(x)A(t)dt。 k1x0

性质8 若cka0bka1bk1akb0，则C(x)ckxkA(x)B(x)。

k0

23x6x2例1 已知an的生成函数为A(x)，求an。

12x

例2 计算级数1222n2的和。

第四节 用生成函数求解递推关系

例1 求递推关系

f(n)7f(n1)12f(n2), f(0)2,f(1)7.解： 令

A(x)f(n)xn，

n0利用给定的递推关系，算得：f(n)3n4n。

5.4.1 用生成函数求解常系数线性齐次递推关系

定理5.4.1 设

P(x)P(x)是有理分式，且多项式P(x)的次数低于Q(x)的次数，则有Q(x)Q(x)分项表示，且表示是唯一的。

5.4.2 用生成函数求解常系数线性非齐次递推关系

例2 求解递推关系

f(n)f(n1)n4, f(0)0.

例3 求解递推关系

f(n)2f(n1)4n1f(1)3.

(n2)

例4 求解卷积形式的递推关系

f(n)f(1)f(n1)f(2)f(n2)f(n1)f(1) (n2)f(1)1.

第五节 生成函数在计数问题中的应用

5.5.1 组合数的生成函数

定理5.5.1 设从ｎ元集合Sa1,a2,,an中取ｋ个元素的组合数为bk，若限定元素出现的ai次数集合为Mi(1in)，则该组合数序列的生成函数为 (xm)。

i1mMin

例１ 求多重集合Mia1,a2,,an的每个ai至少出现一次的ｋ组合数bk。

5.5.2 排列数的指数型生成函数

定理5.5.2 多重集合Mia1,a2,,an的ｋ排列中，若限定元素ai出现的次数集合为Mi(1in)，则排列数的指数型生成函数

(i1nmMixm)。 m!

例２ 多重集合Mia1,a2,,an的ｋ排列数序列的指数行生成函数为

kxx2nkx (1)ee(nx)n1!2!k!k0i1n，从而bknk。

例3 由数字0，1，2，3组成的长为k的序列中，要求含有偶数个0，问这样的序列有多少个？

例4 由1，2，3，4能组成多少个五位数？要求这些五位数中1出现2次或3次，2最多出现1次，4出现偶数次。

例5 求Mia1,a2,,an的ｋ排列中每个ai(1in)至少出现一次的排列数Ai的指数行生成函数。

5.5.3 分拆数的生成函数

定理5.5.3 令B(n)表示正整数ｎ的所有分拆数，Br(n)表示ｎ的各分部量都不超过

r的分拆数，BH(n)表示n的各分部量都属于集合Ｈ的分拆数，则它们相应的生成函数分别为

(1)Br(n)xnn01；

(1x)(1x2)(1xr)(2)BH(n)xnn01； j1xjH(3)B(n)xnn01。 j1xj1

推论5.5.1 将n分成r各分部量的分拆数的生成函数为

xr。

(1x)(1x2)(1xr)

推论5.5.2 n的各分部量两两互不相同的分拆数等于n的各分部量都是奇数的分拆数。

5.5.4 组合型分配问题的生成函数

定理5.5.4 把k各相同的球放入n个不同的盒子a1,a2,an中，限定盒子ai的容量集为Mi(1in)，则其分配方案数的生成函数为

(xi1mMinm)。

例6 求不定方程

x1x2x3x4x520 满足

x13,x22,x34,x46,x50 的整数解个数。

5.5.5 排列型分配问题的生成函数

定理5.5.5 把k个不同的球1,2,,k放入n个不同的盒子a1,a2,an中，限定盒子ai的容量集合为Mi(1in)，则其分配方案数的生成函数为

n(i1mMixm)。 m!

例７ 用红、白、蓝3种颜色给1×n棋盘着色，要求白色方格数是偶数，问有多少种着色方案？

解： 将1n的棋盘的n个方格分别用1，2，，n标记，第i个方格着c色看作是把第i个物体放入c盒中。这时，问题可转换为：把n个不同的球放入3个不同的盒子中，各盒的容量集合分别为

MrMb{0,1,2,}， Mw{0,2,4,}。

于是，分配方案数的指数型生成函数为

x2x2x412(1x)(1)(e3xex)，

2!2!4!21xn其中，的系数(3n1)即为满足要求的着色方案数。

2n!

第六节 有位置的排列及棋子多项式

例1 由5个字母a，b，c，d，e构成的全排列中，a不能出现在1，5位置上，c不能

出现在3，4位置上，e不能出现在5位置上，问有多少种排列方法？

3 1 a b c d e 2 4 5 引理 5.6.1 如果棋盘B分解成两个不相交的子棋盘B1和B2，则

rk(B)ri(Bi)rk1(B2)。

i0k对于棋盘B，定义棋子多项式R(x,B)为数列r0(B),r1(B),的生成函数，即

R(x,B)ri(B)xi。

i0

引理5.6.2 若B1、B2是棋盘B的两个不相交的子棋盘，则

R(x,B)R(x,B1)R(x,B2)。

在前面的例1中，有

R(x,B1)13xx2,R(x,B2)14x3x4, 于是

R(x,B)R(x,B1)R(x,B2)17x16x213x23x4

由此

r1(B)7,r2(B)16,r3(B)13,r4(B)3,r5(B)0， 代入容斥原理的公式，得

N(0)(0)(1)(2)(3)(4)(5)5!74!163!132!31!00!25.

定理5.6.1 在有位置时，安排n个不同物体的 方法数等于

n!r1(B)(n1)!r2(B)(n2)!(1)nrn(B)0!，

其中r1(B),r2(B),,rn(B)是有位置的棋盘B的棋子多项式r(x,B)的系数。

例2 一个小孩给他的3个叔叔A1,A2,A3和3个婶婶U1,U2,U3寄6种贺年卡

C1,C2,C6.，下图列出了每人的好恶，问有多少种让每人都满意的寄送方法？

A1 A2 A3 U1 U2

U3

C1 C2 C3 C4 C5 C6

解： 类似地，可算得寄送方法数为159种。

本章小结：

生成函数是组合数学中求解组合问题的强有力的工具之一，可以用它来求解组合计数问题、证明组合恒等式以及求解递推关系。当用生成函数求解组合计数时，一般说来，若是组合问题应选普通生成函数，若是排列问题应选指数生成函数。 在当代组合数学理论中，生成函数是解决计数问题的重要方法。一方面，生成函数可以看成是代数对象，其形式上的处理使得人们可以通过代数手段计算一个问题的可能性的数目；另一方面，生成函数是无限可微分函数的Taylor级数。如果能够找到函数和它的Taylor级数，那么Taylor级数的系数则给出了问题的解。

第6章 Polya计数理论

第一节 引论

1937年，匈牙利裔数学家G﹒Polya以群论为基础，结合母函数方法建立起一个重要定理—Polya计数定理，它是组合数学中解决一类计数问题的重要理论基础，并被广泛应用。值得一提的是大约在1960年，人们才注意到在Polya的著名文章发表的10年前，H﹒Redfield曾发表过一篇文章，在该文章中就已使用了Polya的基本方法，因此Polya定理也称为Redfield—Polya定理。

Polya计数定理是计数的群论方法中的主要定理，它在化学、遗传学等涉及分子结构的学科中有着重要的应用。事实上，Polya正是为了计数聚合物才证明这一著名定理的。另外，Polya定理在图论、编码理论以及计算机科学等领域也有广泛的应用。

先看下面的例子。

例: 用红,黄两种颜色对正立方体的6个面进行着色,问有多少种不同的方案?

第二节 置换群的基本知识

6.2.1 群和子群

给定集合G和G上的二元运算“”，如果 （1）“”运算在G上是封闭的，即对任意的a,bG都有abG； （2）“”运算满足结合律，即对任意a,b,cG，都有a(bc)(ab)c； （3）存在eG，对任意aG，满足eaaea。称为e的单位元。 （4）对任意aG，存在a1G，满足

aa1a1ae,

a1称为a的逆元。则称代数结构(G,)为群。

设(G,)是群，对于G的元素a，若存在m0，m是满足ame的最小正整数，则称a是m阶元。若这样的m不存在，则称a是无限阶的。如果G是有限集合，则G是群的阶。在n阶群中，任何元素的阶均是n的因子。

设(G,)是群，H是G的非空子集。若对任意的a,bH，abH，且a1H，则称(H,)是(G,)的子群，并记为HG。

注意：当G是有限群时，若G的非空子集H满足对任意的a,bH，有

abH，则H是G的子群。

在群(G,)中，若存在aG，任何G中的元素b均可表示成a的方幂，则称G为循环群，a称为该群的生成元。

6.2.2 置换群

集合{1,2,,n}上的一一映射称为n元置换，记为

2n1

(1)(2)(n)其中，(1),(2),,(n)是{1,2,,n}的一个全排列。令Sn是{1,2,,n}上的置换全体，则显然有Snn!。令1,2是Sn中的两个元素，定义她们的乘积12为

12(i)1(2(i))

它仍是{1,2,,n}上的置换。Sn对于置换乘法“”构成群，称为n次对称群。

(Sn,)的任意子群称为置换群。

例如：

123123123S3,,,123231312123123123,,, 132321213123123123H1,,,

123231312123123H2,

123132都是置换群。

例1 我们取一个正立方体，称之为定体，其顶点集合{1,2,„,8}。设想另一个正立方体与定体完全重合，并且顶点标记相同，称之为动体。动体围绕正立方体的对称轴作各种旋转，使得动体与定体再重合，每一种旋转都确定出顶点{1,2,„,8}上的一个置换，动体的顶点i重合于定体的顶点(i)。这类旋转有如下24种:

(i)不旋转。对应于恒等置换

128I

128确定出18型式置换1个。

4 1 8 5

6 2 3

7

(ii)以相对两面中心联线为轴的旋转。这种轴共有3条，对于每条轴可作90,180和

270共3种旋转。对应的置换分别为

(1234)(5678)，(13)(24)(57)(68),(1432)(5876)。 这类旋转可以确定出42型置换6个，24型置换3个。

4 1 8 5

6 2 3

7

(iii)以相对两顶点联线为轴的旋转。这种轴共有4条，对于每条轴可作120和240两种旋转。对应的置换分别为 (168)(274)，(186)(247)。

这类旋转可以确定出1232型置换8个。

4 1 8 5

对应的置换分别为 (15)(37)(46)(28)。

这类旋转可以确定出24型置换6个。

3 2 7

6

(iv)以相对两边中点联线为轴的旋转。这种轴共有6条，对于每条轴可作180旋转。

这里的24个置换构成S8的一个子群，称为正立方体旋转群，它是8次24阶置换群。

例2 我们取平面上一个正n边形，称之为定盘，其顶点集合为{1,2,„,n}。设想另一个正n边形与定盘完全重合，并且顶点标记相同，称之为动盘。如果只允许动盘作平面旋转，那么绕中心旋转

2i(1in)度，使得动盘与定盘重合。它们对应的nn个顶点集合上的置换是,2,,n1,nI，其中，(12n)。它们构成以为生成元的n次循环群Cn。下图给出了n8的情况。

例3 在例2中,如果允许动盘作平面旋转和空间空间翻转,使得动盘与定盘盘重合,那么,所确定的置换群中除去n个旋转外, 还有n个沿对称轴的翻转.它们构成的顶点

集合上的2n个转换全体称为n次二面体,记作Dn,则

Dn{I,,2,,n1,,,2,,n1}，

其中=(1,2,,n),(1n)(2n1)。

例4 正立方体的24个旋转也确定出6个面构成的集合上的24个置换，它们构成6次24阶置换群。

类似地，正立方体的24个旋转也确定出12条边构成的集合上的24个置换群。

第三节 计算问题的数学模型

定义： 设D,R是有限集合，从D到R映射全体记为

F{f|f:DR}，

G是D上的一个置换群，在F上定义G等价关系：

对任意f1,f2F，若存在G,使得对任意dD， 等式

f1(d)f2(1(d))

均成立，则称f1与f2是G等价的。

G等价关系是F上的等价关系，即它满足：

(1)自反性。 (2)对称性。 (3)传递性。

例1 对正立方体的6个面进行红，黄两色着色。着色方案全体F{f|f:DR}，其中,D{上,下,左,右,前,后},R{红,黄}。f1和f2分别是将上，下和左，右两面着红色，其余四面着黄色的着色方案。设G是D上的置换群(见6.2节例1)，其中有以前，后两面中心联线为轴沿顺时针方向旋转90o的置换{上,右,下,左}，见表6.3.1。可以看出，f1与f2是G等价的,即它们是相同的着色方案。上述数学模型正好反映了我们的直觉。

d 上 下 左 右 前 后 f1 红 红 黄 黄 黄 黄 黄 黄 红 红 黄 黄 左 右 上 下 前 后 红 红 黄 黄 黄 黄 f2 (d) f2((d))

例2 用r个字母能组成多少个长为n的环形字?

例3 用r种颜色的珍珠能组成多少种长为n的项链?

第四节 Burmside 引理

定义： 设G是Sn的子群，在Sn上定义关系G共轭:对任意s,tG，若存在gG,使得sg1tg，则称s与t是G共轭的。 共轭关系的等价关系,即它满足: (1)自反性；(2)对称性；(3)传递性。

引理6.4.1 两个置换s,tSn关于Sn是共轭的，当且仅当它们是同型的。

引理6.4.2 Sn中属于1b12b2nbn型的元素个数为

n!。

b1!b2!bn!1b12b2nbn

6.4.1 共轭类

定义： 设G是Sn的子群，在Sn上定义关系G共轭:对任意s,tG，若存在gG,使得sg1tg，则称s与t是G共轭的。

G共轭关系的等价关系,即它满足:(1)自反性；(2)对称性；(3)传递性。

引理6.4.1 两个置换s,tSn关于Sn是共轭的，当且仅当它们是同型的。

6.4.2 k不动置换类

定义： 设G是{1,2,„,n}上的置换群，令

ZK{|G,(k)k}

是G中元素k保持不置换全体。IZk,Zk是群G的非空子集。又G是有限群，且若1,2Zk, 则

12(k)1(2(k))1(k)k，

所以1,2Zk。故Zk是G的子群,称之为G的k不动置换类。

例：S4中使1保持不动的置换全体

Z1{I,(23),(24),(34),(234),(243)}

是S4的子群。

6.4.3 等价类

设G是D{1,2,,n}上的置换群。在D上定义G等价关系：对任意的k,lD，若存在G，使得(k)l，则称k与l是G等价的。

G等价关系是D上的等价关系，由该关系确定的D上的等价类称为G诱导出来的等价类。元素k所在的等价类记为Ek。

引理6.4.3 如上定义的G,Zk,Ek满足

EkZkG(1kn)。

6.4.4 Burnside引理

引理6.4.4(Burnside 引理) 设G{a1,a2,ag}是{1,2,,n}上的的置换群，则G诱导出来的等价类个数为

1glc1(ai) |G|i1其中，c1(ai)表示在置换ai作用下保持不变的元素个数。

例1 G={ I,(14)(23),(12)(34)(56),(13)(24)(56)}是D{1,2,3,4,5,6}上的置换群,且

有

c1(I)6,c1((14)(23))2,c1((12)(34)(56))0,c1((13)(24)(56))0,

1(6200)2。 4由Burnside引理,G诱导出来的等价类个数为l

例2 对正方形的4个顶点进行红,蓝两色着色,问有多少种不同的着色方案?

第五节 映射的等价类

定义： 对集合R中的每个元素ci赋予一个权(ci),(ci)可以是数字或字母，对

(ci)可以进行加法(+)和连接()运算，并且这些运算满足结合律和交换律。映射

f:DR的权是所有像的权的连接，即

w(f)(f(d)) 。

dD若F是F的子集,则F的权为

w(F)

fF(f) 。

例 设D{1,2,3},R{c1,c2,c3}。定义w(c现)=v,3w(c。)=w有映射1)=u,w(c2，（见表6.5.1），则 f1,f2,f3:DRw(f1,f2,f3)=uv2+u2v+uvw。

表6.5.1 f 1 2 3 c1 c2 c2 f1 c1 c2 c1 f2 f3 c2 c1 c3 W(f) uv2 u2v uvw

注意： 同一个等价类中的映射有相同的权。但是，具有相同权的映射不一定在同一个等价类中。

例1 设D{1,2,3},R{c1,c2,c3}，w(c1)=r,w(c2)=b,w(c3)=g。则rbg表示D中一个元素着色的方式，(r+b+g)3给出了D中三个元素着色的方式

(r+b+g)3=r3+b3+g3+3r2b+3r2g+3b2r+3b2g+3g2r+3g2b+6rgb,

其中3b2g表示对两个物体着颜色b对一个物体着颜色g的方式有3种（见表）。

物体 方式1 方式2 方式3

1 2 3 b b g b g b g b b 例2 现有8个人计划去访问3个城市，其中有3个人是一家，另外有2个人是一家。如果一家人必须去同一城市，问有多少种方案？写出它们的模式。

解： 总的模式为：

(333)(222)()3。

一般地，设D1,D2,,Dk是集合D的一个k分划，若要求映射在子集Di中的所有元素取值相同，则这些映射构成的模式表为：

i(w(r))。 kDi1rR

6.6 Polya 计数定理

令D{1,2,,n},R{c1,c2,,cm}，G是D上的置换群。从D到R的映射

F{f|f:DR}F中权为wi的映射全体构成 ，

Fi{f|fF,w(f)wi}。

对于G中的每个置换，定义i如下：对任意的f1Fi，若由f1与确定了一个从

D到R的的映射f2，即对任意dD，有f2(d)f1(1(d))，则(i)(f1)f2。由

f2的定义可知，对任意dD，有f1(d)f2((d))，故f1与f2是G等价的。又由前述w(f2)w(f1)wi，i是Fi上的映射。

引理6.6.1 映射(i) 是Fi上的置换。

引理6.6.2 对任何1,2G，均有

(i)(21)(i)21(i)。

定理6.6.1 令G是D{1,2,,n}上的置换群，R{r1,r2,,rm}，

F{f|f:DR}，则F上的全部模式表为

2nP(w(r),w(r),,w(r))。 GrRrRrR而

PG(x1,x2,,xn)

1GG,为1b12b2nbn型bnb1b2x1x2xn。

例1 将正三角形的3个顶点用红,蓝,绿3种颜色进行着色,问有多少和不同的方案?如果

(1)经旋转能重合的方案认为是相同的； (2)经旋转和翻转能重合的方案认为是相同的。

解： （1）D{1,2,3}，D上的置换群为

G{I,(123),(132)}， 其轮换指标为

1PG(x1,x2,x3)(x132x3)。

3于是等价类的个数为

1PG(3,3,3)(3323)11。

3（2）只须将（1）的置换群换为

G{I,(123),(132),(13),(12),(23)}， 其轮换指标为

1PG(x1,x2,x3)(x132x33x1x2)，

6于是等价类的个数为

1PG(3,3,3)(3323332)10。

3

例2 对正立方体的6个面有红,蓝,绿3种颜色进行着色,问有多少种不同的方案?又问3种颜色各出现2次的着色方案有多少种?

解： 轮换指标为

PG(x1,,x6)16223(x16x12x43x12x28x36x2)， 24等价类的个数为

PG(3,,3)57。

F的全部模式表

1[(rbg)66(rbg)2(r4b4g4)3(rbg)2(r2b2g2) 248(r3b3g3)26(r2b2g2)3]。

其中，红色、蓝色和绿色各出现两次的方案数就是上述展开式中r2b2g2项的系数，经计算为6。

例3 骰子的6个面上分别标有1,2,„,6,问有多少种不同的骰子?

例4 将两个相同的白球和两个相同的黑球放入两不同的盒子里，问有多少种不同的放法？列出全部方案。又问每盒中有两个球的放法有多少种？

例5 三元布尔函数可以看成是有三个输入端的布尔电路，而一个布尔电路通过交换输入端可以表示多个布尔被函数。求实现所有三元布尔函数需要多少个布尔电路？

例6 求n个顶点的简单图有多少个?

本章小结：

Burnside引理是William Burnside 给出的。这个引理给出了利用置换群中每个置换的不动点的个数，来计算置换群不同轨道数目的公式。但当群的元素的数目较大时，利用Burnside引理进行计算将非常麻烦，这时必须运用Polya定理。大致

说来，运用Polya定理的步骤是， 首先写出问题所对应的置换群，然后根据置换群中元素的类型写置换的类型，并进行归类计算，三是写出轮换指标，最后依据定理计算等价类的个数。