《组合数学》讲稿2015

2023/2/4组合数学1组合

数

学主讲教师邓毅雄2023/2/4组合数学2什么是数学？数学是研究现实中数量关系和空间形式的科学.

---恩格斯

数学是科学之母。数学教育的意义？作为工具的数学，作为素质训练的数学数学是思维的体操数学知识可以记忆一时,但数学的精神、思想和方法却随时随地发挥作用，可以受益无穷.

2023/2/4组合数学3数学是美的吗？哪里有数,哪里就有美.

---恩格斯（学会欣赏数学？）数学的应用？任何一门科学,只有当它充分地应用了数学时才算很好地发展了.

---马克思

2023/2/4组合数学4

在计算机出现以来，数学科学与计算机科学就始终密不可分。国内外许多著名计算机专家是数学出身。

一方面，数学在计算机科学发展中起不可替代的作用。计算机科学的数学理论体系是相当庞杂的，主要有数值计算，离散数学，数论，计算理论等。2023/2/4组合数学5

另一方面，使用计算机解决数学问题（和解决其他问题一样）可能发展出一些新方法。例如先提出假说，用计算机做先期检验，可能是各种简化情况的检验，以考验假说的可能性。然后再考虑如何从理论上严格处理。计算机的图形处理能力、数值计算能力和符号计算能力都可能在处理数学问题的过程中发挥作用。吴文俊院士的数学机械化研究。

2023/2/4组合数学6中国软件发展与组合数学

在美国有一种说法，将来一个国家的经济实力可以直接从软件产业反映出来。

纵观全世界软件产业的情况，美国处于绝对的垄断地位。造成这种现象的一个根本的原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究组合数学出身的。美国的软件之所以能领先，其关键就在于在数学基础上他们有很强的实力，有很多杰出的人才。美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，….）都有一流的组合数学家。2023/2/4组合数学7

我国在软件上的落后，要说出根本的原因可能并不是很简单的事，除了技术和科学上的原因外，可能还跟我们的文化，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础十分薄弱，这个问题不解决，我们就难成为软件强国。组合数学是研究离散对象的数学分支，它是随着计算机出现及其普遍应用才迅速发展起来的，组合数学的发展奠定了本世纪的计算机革命的基础。2023/2/4组合数学8

高层次的软件产品处处用到组合数学，更确切地说就是组合算法。计算机算法可以分为三大类，（一）组合算法，（二）数值算法（包括计算数学和与处理各种信息数据有关的信息学），（三）符号计算算法。（前两者是传统的，后者是最近发展的）吴文俊院士开创的机器证明方法就属于符号计算，引起了国际上的高度评价，被称为吴方法。符号算法和吴方法跟代数组合学也有十分密切的联系。由于数学机械化近年来的发展和在计算机科学中的重要性，把数学机械化，科学计算和组合数学组合起来，就可以说是中国信息产业的基础2023/2/4组合数学9

今后的计算机要向更加智能化的方向发展，其出路仍然是数学的算法和数学的机械化。

美国著名数学家、科学院院士、世界著名组合大师Gian-CarloRota教授指出：组合数学是计算机软件产业的基础，中国最终一定能成为一个软件大国，但是要实现这个目标的一个突破点就是发展组合数学。（陈永川）

胡锦涛同志在1998年接见"五四"青年奖章时发表的讲话中指出，组合数学不同于传统的纯数学的一个分支，它还是一门应用学科，一门交叉学科。他希望中国的组合数学研究能够为国家的经济建设服务。

2023/2/4组合数学10吴军博士《数学之美》

自然语言处理搜索2023/2/4组合数学11

组合数学(Combinatorialmathematics)是一个古老而又年轻的数学分支。 据传说，大禹在4000多年前就观察到神龟背上的幻方…...2023/2/4组合数学12

幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。5193724862023/2/4组合数学13

组合数学主要研究满足一定条件的组态（一种安排）的存在性、计数及构造等方面的问题。组合数学大体上可分为组合计数、组合设计、组合矩阵、组合优化等方面。组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。但是，由于组合数学的方法往往具有一定的技巧性，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。2023/2/4组合数学14参考教材：卢开澄《组合数学》2023/2/4组合数学15第一部分

排列和组合2023/2/4组合数学16一、计数原则

(一)相等原则[例]100名选手参加网球单打赛，需要打多少场比赛才能产生冠军？相等原则：设A，B是两个有限集，如果存在由A到B上的一个一一对应映射，则|A|＝|B|。（这里|A|表示有限集A所含元素的个数，以后也类同）相等原则主要用于：将较复杂的计数问题转化为较简单的计数问题。2023/2/4组合数学17(二)加法原则[加法法则

] 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言： 若|A|=m,|B|=n,A∩B=,则

|A∪B|=m+n。2023/2/4组合数学18[例]

某班选修企业管理的有18人，不选的有10人，则该班共有

18+10=28人。[例]

北京每天直达上海的客车有5次，客机有3次，则每天由北京直达上海的旅行方式有

5+3=8种。2023/2/4组合数学19[例]

设n为大于1的正整数，求满足x+y≤n的有序正整数对（x,y）的个数。因此，由加法原则：所求有序对个数为：

N＝（n-1)+(n-2)+…+1

＝n(n-1)/2。解：当x＝1时，所有可能的有序对有n－1个；当x＝2时，所有可能的有序对有n－2个，…当x＝n－1时，所有可能的有序对有1个。2023/2/4组合数学20[乘法法则

] 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有m·n种产生方式。集合论语言：若|A|=m,|B|=n,AB={(a,b)|aA,bB},

则|AB|=m·n。(三)乘法原则2023/2/4组合数学21[例]

某种字符串由两个字符组成，第一个字符可选自{a，b，c，d，e}，第二个字符可选自{1，2，3}，则这种字符串共有

53=15个。[例]从A到B有三条道路，从B到C有两条道路，则从A经B到C有

32=6条道路。2023/2/4组合数学22[例]由数字1,2,3,4,5，（1）可以构成多少个数字不同的四位数？（2）可以构成多少个四位偶数？（3）可以构成多少个数字不同的四位偶数？解：（1）其个数为：5×4×3×2＝120；（2）其个数为：5×5×5×2＝250；（3）其个数为：4×3×2×2＝48。2023/2/4组合数学23[例]

某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有

42=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是44=16，而只有43=12种。在乘法法则中要注意事件A和事件B的相互独立性。2023/2/4组合数学24[例]求n元集合A＝｛a1,a2,…,an｝的子集的个数。解：经过n步来构造，每步对应元素两种选择：选取或不选取。也就是说，这n步中，每步均有两种方法，所以总共有2n种方法，即n元集合A的子集的个数为2n。推广：设有集合A＝｛k1·a1,k2·a2,…,kn·an｝，其中ki·ai

（i=1,2,…,n）表示A中有ki个ai。求集合A的子集的个数。2023/2/4组合数学25设n为正整数，p1，p2,…pk是互不相同的素数，若则整除n的正整数的个数为：如300＝22·3·52，则整除300的正整数的个数为：2023/2/4组合数学26(一)n元集的r－排列定义：从n个不同的元素构成的集合中，任取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的个数用P(n,r)或Prn表示。一个排列也可看作一个字符串，r也称为排列或字符串的长度。

一般不说可重即无重。二、排列2023/2/4组合数学27

从n个中取r个的排列的典型例子（模型）是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，······，第r个有n-r+1种选择。故有

P(n,r)=n(n-1)······(n-r+1)当r=n时称为全排列,记为n!。0！＝12023/2/4组合数学28

上述（无重）排列的计数相当于将r个不同的球（将r个球编为1号到r号）放入n个不同的盒子，每盒最多一个球的方案数。公式：2023/2/4组合数学29[例]

用五种颜色给三个点着不同的色，问有多少种不同的着色方案？解：着色方案数为：P(5,3)＝5×4×3＝60种。[例]乒乓球队的10名队员中有3名主力队员，派5名参加比赛。3名主力队员要安排在第一、三、五位置，其余7名队员选2名安排在第二、四位置，那么不同的出场安排共有多少种？解：安排的种数为：

3！P（7，2）＝252。2023/2/4组合数学30[例]由5种颜色的星状物，20种不同花排成如下的图案：两边是星状物，中间是3朵花。问有多少种这样的图案？解：设所求为N。5种颜色的星状物取两种排列的排列数为：

P(5,2)=5×4=20；20种不同花，取3种排列的排列数为：

P(20,3)=20×19×18=6840。由乘法原则，N=20×6840=136800。2023/2/4组合数学31[例]求20000到70000间的偶数中由不同数字组成的5位数的个数。解：设所求为N。若所求的数为abcde这5位数，其中2≤a≤6，e∈{0,2,4,6,8}。①若a∈{2,4,6}，则e有4种选择，bcd有P(10-2,3)=P(8,3)种选择，由乘法原则，有

3×4×P(8,3)=4032种可能；②若a∈{3,5}，则e有5种选择，bcd有P(10-2,3)=P(8,3)种选择，由乘法原则，有2×5×P(8,3)=3360种可能。由加法原则，N=4032＋3360＝7392。2023/2/4组合数学32〔例〕求由n个相异元素a1，a2，…，an构成的a1与a2不相邻的全排列的个数。解：n个元素的全排列种数为n！，其中a1与a2相邻的全排列的个数为2(n-1)!，所以，满足题意的全排列个数为：

n!-2(n-1)!=(n-2)(n-1)!。2023/2/4组合数学33(二)n元集的r－可重复排列定义：设A是n元集，如果序列a1a2…ar的元素都属于A，则称该序列是n元集A的一个r－可重复排列。如设A＝{1,2,3,a,b},则123aabb是A的一个7－可重复排列；aa13b222bb是A的一个10－可重复排列。问题：这种可重复排列的个数有多少呢？2023/2/4组合数学34定理：

n元集的r－可重复排列的个数为nr。证明：（略）[例]

由1,2,3,4,5,6可组成多少个大于35000的5位数？解：分两种情况考虑：①万位数字为3的5位数：此时千位必为5或6，有

2×63＝432个；②万位数字大于3的5位数：此时万位是4，5，或6，有

3×64＝3888个。由加法原则：共有432＋3888＝4320个。2023/2/4组合数学35(三)多重集的排列定义（多重集）：由n1个a1，n2个a2，…，nk个ak，组成的集合M，记为

M＝{n1·a1，n2·a2，…，nk·ak}，称为多重集。如果n＝n1＋n2＋…，＋nk，也称M为n－多重集。如：M＝{4·a1，3·a2，2·a3}M＝{3·1，4·2，2·3,2·4}2023/2/4组合数学36定义（多重集的排列）：设

M＝{n1·a1，n2·a2，…，nk·ak}，π是集合A＝{a1，a2，…，ak}的一个n－可重复排列且π中有n1个a1，n2个a2，…，nk个ak，则称π为多重集M的一个全排列，也称π为由n1个a1，n2个a2，…，nk个ak构成的全排列。如：M＝{3·a1，2·a2，3·a3}，π1＝a1a1a2a2a3a3a1a3是M的一个8－可重复排列；

M＝{3·1，4·2，2·3,2·4}，π2＝24113423221是M的一个11－可重复排列。

问题：这种可重复排列的个数？2023/2/4组合数学37定理：多重集M＝{n1·a1，n2·a2，…，nk·ak}的全排列的个数为：证明：设M的全排列的个数为x。以M’表示把M中的所有相同元素换成互不相同的元素，即M’是由n1＋n2＋…＋nk个互不相同元素组成的集合。M’中元素的全排列的个数为(n1＋n2＋…＋nk)！，M’全排列也可以这样得到：先作M的全排列，其排列数为x；再将M中全排列的相同元素换成互不相同的元素，如n1个a1换成不同元素的排列数为n1！，其余类似。由乘法原则，这样构造的M’的全排列数为x·n1！n2!...nk！。由相等原则：(n1＋n2＋…＋nk)！＝x·n1！n2!...nk！，因此2023/2/4组合数学38例如：

M＝{3·a1，2·a2，3·a3}的全排列个数为

M＝{3·1，4·2，2·3,3·4}的全排列个数为：2023/2/4组合数学39(四)圆周排列问题：从n个对象中取r个沿一圆周排列，求不同的排列种数。记号计算公式：2023/2/4组合数学40[例]5对夫妻出席一宴会，围一圆桌坐下，试问有多少种不同的坐法？若要求每对夫妻相邻又有多少种坐法？

Q(10,10)=9!=362880;Q(5,5)·25=4！·25=768。2023/2/4组合数学41三、格路模型1.定义(棋盘)：由p×q个单位正方形拼成的长为p，宽为q的长方形叫做一个p×q棋盘。一个10×5的棋盘OP从O到P的一条路径2023/2/4组合数学422.简单格路问题：从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？y(m,n)...0...x2023/2/4组合数学43无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。则(0,0)→(m,n)的每一条路径可表示为m个x与n个y的一个多重排列。即为多重集

M={m·x,n·y}的全排列，根据前面的结论，其全排列数为相等原则2023/2/4组合数学44定理(格路计数)：沿p×q棋盘上的线段，由点O(0,0)到点M(m,n)的格路的数目为：如从(0,0)到(3,7)的格路数目为：2023/2/4组合数学45推广：设c≥a,d≥b,则由A(a,b)到B(c,d)的格路数为

B(c,d)A(a,b)如：从点(2,4)到点(7,6)的格路数为：2023/2/4组合数学46(一)n元集的r－组合定义(r－组合)：集合A的含r个元素的子集称为A的一个r－组合。组合的全体组成的集合用C(n,r)表示，所有可能的r－组合的个数也用C(n,r)或表示。

组合的计数相当于将r个不相同的球放入n个相同的盒子里，每盒最多一个球的方案数。

四、组合2023/2/4组合数学47

若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有

C(n,r)·r!=P(n,r),

C(n,r)=P(n,r)/r!=(

)=即：nrn!———r!(n-r)!从(0,0)到(m,n)格路数：2023/2/4组合数学48[例]有5本不同的法文书，7本不同的英文书，10本不同的中文书。

1)取2本不同文字的书；

2)取2本相同文字的书；

3)任取两本书。解：1)5×7+5×10+7×10=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;3)155+76=231=C(5+7+10,2)2023/2/4组合数学49[例]甲和乙两单位共11个成员，其中甲单位7人，乙单位4人，拟从中组成一个5人小组：（1）若要求必须包含乙单位2人；（2）若要求至少包含乙单位2人；（3）若要求乙单位某一人与甲单位特定一人不能同时在这个小组。试分别求各有多少种方法。解：（1）（2）2023/2/4组合数学50（3）不妨设甲单位A与乙单位B不能同时在小组。首先A与B同时在小组的情形有所以所求为：2023/2/4组合数学51[例]

从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？解将[1,300]分成3类：

A={i|i≡1(mod3)}={1,4,7,…,298},B={i|i≡2(mod3)}={2,5,8,…,299},C={i|i≡0(mod3)}={3,6,9,…,300}.

要满足条件，有四种解法：

1)3个数同属于A;

2)3个数同属于B；

3)3个数同属于C;

4)A,B,C各取一数.故共有3C(100,3)+1003=485100+10000002/4组合数学52【例】10个节目中有6个演唱、4个语言类。今编写节目单，要求任意两个语言类之间至少有1个演唱，问可编写出多少种不同的演出节目单?解：设可编写出N种不同的演出节目单．可依如下三个步骤去编写节目单：①作6个演唱节目的全排列．有6！=720种方法；②从作成的排列的左边、右边及6个元形成的5个空隙这7个位置甲选出4个位置中选出4个位置，有C(7,4)=35种方法；③把4个语言类节目放在巳选出的4个位置上，每个位置放一个语言类节目，有4！=24种方法.

由乘法原则得

N=720×35×24=604800。2023/2/4组合数学53【例】今安排7人人住某旅馆的5个房间．每个房间至少安排1入，有多少种不同的安排住宿的方法?由加法原则得N=4200+12600=16800种。②有两个房间均安排2人入住的住宿方法．属于此类住宿方法：种，解：设有N种不同的安排住宿方法，这些方法可分成如下两类：①有1个房间安排3人入任的住宿方法：

种，2023/2/4组合数学54(二)n元集的r－可重复组合定义(r－可重复组合)：从集合A中可重复地选取r个元作成的多重集，称为集合A的一个r－可重复组合。

设A＝{a1,a2,…,an}为n元集，则A的任一个r－可重复组合可表成{x1·a1,x2·a2,…,xn·an}，其中xi为非负整数，且x1+x2+…+xn=r。如A={a,b,c,d,e}，｛a,a,b,c,c,c,d,e,e｝={2·a,1·b,3·c,1·d,2·e}是A的一个9-可重复组合。

问题：A的r－可重复组合的个数？2023/2/4组合数学55A={1,2,3,4}，｛2·1,3·2,2·3,1·4｝

1≤1≤2≤2≤2≤3≤3≤4，

1<1+1<2+2<2+3<2+4<3+5<3+6<4+7即1<2<4<5<6<8<9<11所以｛2·1,3·2,2·3,1·4｝←→｛1,2,3,5,6,8,9,11｝。从A={a,b,c}中，可重复取6个的组合数为：2023/2/4组合数学56A={1,2,3,4,5}，取10-可重复组合：

{1，1，1，2，3，3，3，4，4，5}考虑:构造与此可重复组合对应的一个不可重复组合

{1，1，1，2，3，3，3，4，4，5}{1，1+1，1+2，2+3，3+4，3+5，3+6，4+7，4+8，5+9}{1，2，3，5，7，8，9，11，12，14}这个10-可重复组合相当于从

A’={1,2,3,4,5,6,7,8,9,10,11,12,13,14}中取10个的不重复组合。2023/2/4组合数学57定理(r－可重复组合计数)：n元集的r－可重复组合的个数为：定理的证明：只要证明允许重复的组合与从n+r-1个不同的元素中取r个作不重复的组合是一一对应的。设从n个不同元素中取r个作允许重复的组合：

a1,a2,

…,ar,且a1≤a2≤…≤ar≤n(a1,a2,…,ar)(a1,a2+1,…,ak+k-1,…,ar+r-1)(a1,a2+1,…,ak+k-1,…,ar+r-1)满足

a1<a2+1<…<ak+k-1<…<ar+r-1≤n+r-1,故是从1到n+r-1中取r作不允许重复的组合。2023/2/4组合数学58(三)组合的基本性质1.C(n,r)=C(n,n-r)

从[1,n]去掉一个r子集，剩下一个(n-r)子集。由此建立C(n,r)与C(n,n-r)的一个一一对应。故C(n,r)=C(n,n-r)2023/2/4组合数学592.C(n,k)=C(n-1,k)+C(n-1,k-1)即从[1,n]取a1,a2,…,ak.设1≤a1＜a2＜…＜ak≤n,对取法分类：

a1=1,有C(n-1,k-1)种方案

a1>1,有C(n-1,k)种方案共有C(n-1,k)+C(n-1,k-1)种方案，故

C(n,k)=C(n-1,k)+C(n-1,k-1)2023/2/4组合数学60y(m,n)...0...x(m,n-1)

(m-1,n)上面等式的另外一种形式：

C(m+n,m)=C(m+n-1,m)+C(m+n-1,m-1)可以用格路模型证明：{(0,0)→(m,n)}={(0,0)→(m,n-1)}∪{(0,0)→(m-1,n)}2023/2/4组合数学61由组合的计算公式：2023/2/4组合数学623.()+()+()+…+()=()[证明一]从[1,n+r+1]取a1a2…anan+1，设

a1＜a2＜…＜an＜an+1， 可按a1的取值分类：a1=1,2,3,…r,r+1.a1=1,a2…an+1取自[2,n+r+1]有()种取法nn+1n+2n+rn+r+1nnnnn+1n+rna1=2,a2…an+1取自[3,n+r+1]有()种取法n+r-1n………a1=r,a2…an+1取自[r+1,n+r+1]有()种取法n+1na1=r+1,a2…an+1取自[r+2,n+r+1]有()种取法nn2023/2/4组合数学63[证明二]格路模型：从(0,0)到(n+1,r),过且仅过一条带箭头的边,而过这些边的路径有(从下到上)(),(),…,()故有.(

)+()+()+…+()=()nn+1n+rnnnnn+1n+2n+rn+r+1nnnnn+1r(n+1,r)

...(0,0)nn+12023/2/4组合数学644.()()=()()①选政治局,再选常委,n个中央委员选出m名政治局委员,再从其中选出k名常委②选常委,再选非常委政治局委员两种选法都无遗漏,无重复地给出可能的方案，应该相等。nmnn-kmkkm-k2023/2/4组合数学655.

()+()+…+()=2,

证1(x+y)

=∑(

)x

y,令x=y=1,得.组合证1[1,m]的每个元素取与不取，这样有2m

个方案.另外，这样的组合中，可含有0个元素,1个元素,…,m个元素，其方案种数恰为公式的左边.mmmm01m

mkm-k

mmkk=02023/2/4组合数学665.

()+()+…+()=2,

组合证2

从(0,0)走m步有2m

种走法,都落在直线x+y=m上,而到(m,0),(m-1,1),(m-2,2),…,(2,m-2),(1,m-1),(0,m)各点的走法各有(

),(

),(

),…,(

),(

),()种mmmm01m

mmmmmm012m-2m-1m(m,0)(0,m)(m-1,1)2023/2/4组合数学676.()-()+()-…±()=0证1

在(x+y)=∑()xy中令x=1,y=-1即得.nnnn012nnn-kknk

nk=02023/2/4组合数学68证2

在[1,n]的所有组合中,含1的组合←→不含1的组合.有1—1对应关系。在任一含1组合及与之对应的不含1组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集，将含偶数个元的组合做成另一集。此二集的元数相等。 ∑(

)=∑(

)nniii奇i偶2023/2/4组合数学697.()=()()+()()+…+()()即Vandermonde恒等式证1

从m个互异红球和n个互异蓝球中取r个球,按r个球中红球的个数分类.组合证法:(0,0)到(m+n-r，r)点的路径.(0,0)→(m-r+l,r-l)→(m+n-r,r)

(

)()()=∑()()m+nmnmnmnr0r1r-1r0mnr-llm+nmnrr-llP(m-r,r)(m+n-r,r)(m-r+l,r-l)l=0,1,2,…,r

Q(m,0)

rl=02023/2/4组合数学70李善兰(1811—1882），清代数学家李善兰恒等式： ∑()()()=()()kln+k+l-jn+kn+ljjk+lklj≥0证：利用Vandermonde恒等式及

()()=()()=()() (接下页)nvnn-pnn-pvppn-vpv-p2023/2/4组合数学71有∑()()()=∑()()(∑()())=∑()∑()()()=∑()∑()()()=∑()()()=∑()()()=()∑()()=()()kln+k+l-jjjk+lkln+kl-jjjk+vl-vn+kkll-jk+vjjl-vn+kklvk+vjvln+klk+vk+vvkn+knlkn-vvn+knlkn-vvn+kn+lkl

j≥0j≥0v≥jv≥0j≥0v≥0j≥0v≥0v≥0v≥02023/2/4组合数学72

五、多项式定理定理(多项式定理)：设n是正整数，x1,x2,…,xk是任意k个实数，则多重集｛n1·x1,n1·x2,…,nk·xk｝的全排列数？2023/2/4组合数学73证明:(x1+x2+…+xk)n是n个因子(x1+x2+…+xk)的乘积，其展开式中共有kn项。设是展开式中任一项，如果在中有n1个x1，n2个x2，…，nk个xk(n1+n2+…+nk=n)，则把归于(n1,n2,…,nk)类。显然，属于(n1,n2,…,nk)类的项的个数等于因此展开式中的系数为2023/2/4组合数学74推理(二项式定理)：设n是正整数，x和y是任意实数，则例如：2023/2/4组合数学75求中x5的系数x5的系数为2023/2/4组合数学76令x=y=1，得到令x=-1和y=1得到2023/2/4组合数学77[例]求证：证明：（1）由于(1+x)n·(1+x)m=(1+x)n+m,则比较上式两边xr的系数，得：2023/2/4组合数学78（2）在（1）的式子中，令m=r=n，得即2023/2/4组合数学79[例]求证：证明：令则f(0)=0,利用幂级数的可导性2023/2/4组合数学80则上式两边积分得：所以从而2023/2/4组合数学81[例]求证：证明：证明：当n=m时，结论成立。当n>m时，2023/2/4组合数学82六、T路定义(T步)：在Oxy坐标平面上，横坐标与纵坐标都是整数的点称为整点。由任一个整点(x,y)到整点(x+1,y+1)或(x+1,y-1)的有向线段称为一个T步。(x,y)(x+1,y+1)(x+1,y-1)2023/2/4组合数学83定义(T路)：由整点A到整点B的一条T路是指由若干个T步组成的起点为A、终点为B的有向折线。A··

B并不是任意两点之间都有T路·C·D2023/2/4组合数学84定理(T条件)：如果存在由整点A(a,α)到整点B(b,β)的T路，则①b>a,②b-a≥∣β－α∣，③a+α与b+β的奇偶性相同。（上述三个条件称为T条件）A(a,α)··

B(b,β)2023/2/4组合数学85AB设A(a,α)，B(b,β)DC2023/2/4组合数学86设A(a,α)，B(b,β)XYO2023/2/4组合数学87定理(T路的计数)：设整点A(a,α)与整点B(b,β)满足T条件，则由A到B的T路的数目为：从A(2,1)到B(7,4)的T路数目为：由相等原则和格路计数公式：如从(0,0)到(6,2)到T路数：2023/2/4组合数学88A●●BA’●设A(a,α)，B(b,β),A’(a,-α)每一条从A到B且经过x轴的T路，一一对应一条从A’到B的T路2023/2/4组合数学89七、反射原理定理(反射定理)：设整点A(a,α)与整点B(b,β)满足T条件，且α>0,β>0,b-a≥α+β，则由A到B且经过x轴（即与x轴有交点）的T路的条数等于由A’(a,-α)到B的T路的条数，为：如：从(1,1)到(8,4)且经过x轴到T路数：2023/2/4组合数学90定理：设整点A(a,α)与整点B(b,β)满足T条件，且α>0,β>0,b-a≥α+β，则由A到B且不经过x轴的T路的条数为：2023/2/4组合数学91[例]甲、乙两人进行乒乓球比赛，最后比分为21:17，求在比赛过程中的记分情形的种数。解：设所求为N。一种记分情形唯一确定了一个数列a1a2…a38，其中以Aj表示点(j,a1+a2+…+aj)(j=1,2,…,38)，则比赛记分情形可用有向折线表示。2023/2/4组合数学92所以N等于由点(1,1)到点(38,4)的T路的条数，为：又Aj+1与Aj(j=1,2,…,38)横坐标之差为1，纵坐标之差为其值为1或-1，故是一个T步，从而是从A1(1,1)到A38(38,4)且不经过x轴的T路。Aj●●

Aj+1●

Aj+12023/2/4组合数学93[例]甲、乙两人进行乒乓球比赛，最后比分为21:17，求在比赛过程中甲总是领先于乙的记分情形的种数。解：设所求为N。一种记分情形唯一确定了一个数列a1a2…a38，其中以Aj表示点(j,a1+a2+…+aj)(j=1,2,…,38)，则比赛记分情形可用有向折线表示。由于甲的得分始终高于乙，故Aj的纵坐标大于零。又Aj+1与Aj(j=1,2,…,38)横坐标之差为1，纵坐标之差为其值为1或-1，故是一个T步，从而是从A1(1,1)到A38(38,4)且不经过x轴的T路。2023/2/4组合数学94所以N等于由点(1,1)到点(38,4)且不经过x轴的T路的条数，为：2023/2/4组合数学9517.甲、乙两人竞选厂长，甲得选票a张，乙得选票b张，a>b，问在点票过程中甲的得票恒领先于乙的情形有多少种？解：用Aj(j=1,2,…,a+b)表示点(j,a1+a2+…+aj)，其中则满足题意的点票过程可用有向折线表示。显然，Aj(j=1,2,…,a+b)是整点。由于在点票过程中甲的得票恒领先于乙，故Aj的纵坐标大于0，而Aj+1(j=1,2,…,a+b－1)与Aj的横坐标之差为1，纵坐标之差为1或－1，故是一个T步，从而2023/2/4组合数学96

是由A1(1,1)到Aa+b(a+b,a-b)且不经过x轴的一条T路。于是不同的点票情形的种数等于由整点(1,1)到整点(a+b,a-b)且不经过x轴的T路的条数，为：2023/2/4组合数学97定理：(1)由点O(0,0)到点V(2n,0)，中途不经过x轴且位于上半平面的T路的条数为：(2)由点O(0,0)到点V(2n,0)，且位于上半平面的T路的条数为：OV(2n,0)2023/2/4组合数学98定理：(1)由点O(0,0)到点V(2n,0)，中途不经过x轴且位于上半平面的T路的条数为：(2)由点O(0,0)到点V(2n,0)，且位于上半平面的T路的条数为：OV(2n,0)xyX’O’2023/2/4组合数学99八、卡塔兰(Catalan)数一个凸n＋1边形,通过不相交于n＋1边形的对角线,把n＋1边形拆分成若干三角形,不同拆分的数目用Cn表之.例如五边形有如下五种拆分方案，故C4＝52023/2/4组合数学100(n=1,2,…)称为Catalan数。由前面的定理知，Cn也是由点O(0,0)到点V(2n,0)，中途不经过x轴且位于上半平面的T路的条数。下面给出Catalan数的另外一种解释：某种方程解的个数一般地：八、卡塔兰(Catalan)数2023/2/4组合数学101定理：设S2n表示满足条件的解(x1,x2,…,x2n)的集合，则定理：设T2n表示满足条件的解(x1,x2,…,x2n)的集合，则2023/2/4组合数学102定理：设S2n表示满足条件的解(x1,x2,…,x2n)的集合，则证明：用K表示从点A0(0,0)到点A2n(2n,0)，中途不经过x轴且位于上半平面点全部T路的集合，则下面构造K与S2n的一一对应关系2023/2/4组合数学103设s∈S2n，且s=(x1,x2,…,x2n)。记

Aj(j,j-2x1-2x2-…-2xj)，依题意，Aj(j=1,2,…,2n)是整点且当1≤j≤2n－1时，j-2x1-2x2-…-2xj>0，则Aj在x轴的上方。

又因为Aj+1与Aj的横坐标之差为1，纵坐标之差为(j+1-2x1-2x2-…-2xj+1)-(j-2x1-2x2-…-2xj)=1-2xj+1,其值为1或－1，所以是一个T步。2023/2/4组合数学104

从而且ls由s唯一确定。作由S2n到K到映射显然φ是一个从S2n到K到一一对应映射。由相等原则，由2023/2/4组合数学105[例]甲、乙两对进行手球比赛，最后比分为20:20，求在比赛过程中甲队总是领先于乙队的记分情形的种数。解：设所求为N。比赛记分情形可用由0和1作成的长为40的有序数组(x1,x2,…,x40)表示，其中依题意有所以N等于上述方程解的个数，为：2023/2/4组合数学106[例]甲、乙两对进行手球比赛，最后比分为20:20，求在比赛过程中甲队总是不落后于乙队的记分情形的种数。解：设所求为N。比赛记分情形可用由0和1作成的长为40的有序数组(x1,x2,…,x40)表示，其中依题意有所以N等于上述方程解的个数，为：2023/2/4组合数学107第二部分

母函数与递推关系2023/2/4组合数学108本章学习目的

掌握母函数的基本性质，用普通型母函数解线性常系数递推关系，用指数型母函数解某些与排列有关的计数问题，掌握根据实际问题列出递推关系的技巧，掌握解某几种非线性常系数递推关系的方法。

2023/2/4组合数学109一、母函数

递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数还有其他用处，但里这主要是介绍解递推关系上的应用。例如

项的系数中所有的项包括n个元素a1,a2,…an中取两个组合的全体.2023/2/4组合数学110同理x3项系数包含了从n个元素a1，a2，…an中取3个元素组合的全体。以此类推……2023/2/4组合数学111

定义：对于序列构造一函数：称函数G(x)是序列的母函数。例如(1+x)n

是序列的母函数。

序列可记为。

如若已知序列则对应的母函数G(x)便可根据定义给出。反之，如若以求得序列的母函数G(x)，则该序列也随之确定。

2023/2/4组合数学112例：若有红球一只，蓝球、黑球各二只，试求有多少种不同的组合方案。除一个球也不取外：（1）取一个球：3种｛●，●，●｝（2）取两个球：5种｛●●

，●●，●●，●●，●●｝（3）取三个球：5种｛●●

●

，●

●●，●●●

，●

●●，●●●

｝（4）取四个球：3种｛●●

●

●

，●●●●，●

●●●

｝（5）取五个球：1种｛●●

●

●●

｝总共17种组合。2023/2/4组合数学113

显然，令Ci（i=0,1,2,3,4,5,）表示取i个求的组合数，则其对应的母函数为：

G(x)＝1+3x+5x2+5x3+3x4+x5另外，我们注意到，设Gk(x)(k=1,2,3)分别表示只取红、蓝、黑球的组合数对应的母函数，由于考虑同颜色的球是没有区别的，则容易得到：

G1(x)=1+x,G2(x)=1+x+x2,G3(x)=1+x+x2G1(x)G2(x)G3(x)=(1+x)(1+x+x2)(1+x+x2)=(1+2x+2x2+x3)(1+x+x2)=1+3x+5x2+5x3+3x4+x5=G(x)推广到一般？2023/2/4组合数学114例：某单位有2m位男员工，n位女员工。现在要成立一个由偶数个男员工和数目不少于两个的女员工的小组，问有多少种组成方式？偶数个男员工的组合数对应的母函数：

A(x)=C(2m,2)x2+C(2m,4)x4+…+C(2m,2m)x2m不少于两个女员工的组合数对应的母函数：

B(x)=C(n,2)x2+C(n,3)x3+…+C(n,n)xn问题对应的母函数：

C(x)=A(x)B(x)C(X)的展开式的各系数之和即为所求组合数。2023/2/4组合数学1152023/2/4组合数学116[例]若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？解：对应的母函数为：对应项的系数即为所求。2023/2/4组合数学117[例]若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能称出那几种重量？各有几种方案？能称出20种重量，方案数为60（系数之和）。2023/2/4组合数学118[例]若有1、2、4、8、16、32克的砝码各一枚，问能称出那几种重量？有几种可能方案？

从生成函数可以得知，用这些砝码可以称出从0克到63克的重量，而且办法都是唯一的。2023/2/4组合数学119二、 几个常用的母函数

一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。2023/2/4组合数学1202023/2/4组合数学121[例]写出数列的母函数。解：数列的母函数2023/2/4组合数学122[例]求数列an=n(n+3)的母函数。解：数列对应的母函数为：2023/2/4组合数学123[例]已知数列{an}的母函数为求数列{an}。解：由于所以2023/2/4组合数学124三、指数型母函数

定义：对于序列，函数称为是序列的指数型母函数2023/2/4组合数学125两个结论：(a)若元素a1

有n1个，元素a2有n2

个，……，元素ak有nk个，由此；组成的n个元素的排列，不同的排列总数为其中2023/2/4组合数学126

例1：求由两个a，1个b，2个c组成的不同排列总数。

根据结论一，不同的排列总数为2023/2/4组合数学127

(b)若元素a1

有n1个，元素a2

有n2个，……，元素ak有nk个，由此；组成的n个元素中取r个排列，设其不同的排列数为pr，则序列p0，p1，…，pk的指数型母函数为2023/2/4组合数学128

例2：由1，2，3，4四个数字组成的五位数中，要求数1出现次数不超过2次，但不能不出现；2出现次数不超过1次；3出现次数可达3次，也可以不出现；4出现次数为偶数。求满足上述条件的数的个数。

设满足上述条件的r位数为，序列的指数型母函数为2023/2/4组合数学1292023/2/4组合数学130由此可见满足条件的5位数共215个。2023/2/4组合数学131[例]求在多重集A=｛3a,2

b,3

c｝中选取4个进行排列的不同方法种数。解：设从A中选取r个的排列种数为ar，则数列{ar}对应的指数型生成函数为：所以a4＝702023/2/4组合数学132例3:求1，3，5，7，9五个数字组成的n位数的个数，要求其中3，7出现的次数为偶数，其他1，5，9出现次数不加限制。 设满足条件的r位的个数为ar

，则序列a1,a2,a3,…对应的指数型母函数为2023/2/4组合数学133由于2023/2/4组合数学1342023/2/4组合数学135利用递推关系进行计数是组合计数的一种常见方法，也是计算机科学中进行算法设计与分析的重要工具。对数列{an},所谓递推关系，就是数列的前后项之间的关系。如：（1）an=an-1+2,

（2）an-2an-1-an-2=0,

（3）an-4an-1=5n

四、递推关系2023/2/4组合数学136[例]n条无三线共点直线将平面分成了多少个区域？设n条直线将平面分成了Dn个区域。先考虑n－1条直线将平面分成了Dn-1个区域，再将第n条直线加入，这时第n条直线被前n－1条直线分成了n段，这n段正好是新增加的n个区域的一边界。所以Dn=Dn-1+n，其中D1=2。2023/2/4组合数学137

[例]汉诺(Hanoi)塔问题：这是个组合数学中的著名问题。n个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。

ABCABC

初始状态最终状态2023/2/4组合数学138这是在十九世纪末，欧洲风行的一种游戏。并大肆宣传说，布拉玛神庙的教士所玩的这种游戏结束之日就是世界毁灭之时。（为什么这样说？）Hanoi问题对于计算机科学来说也是个典型的问题，解决问题的第一步要设计算法，进而估计它的复杂性，即估计工作量。

算法：N=2时

，先把上面的圆盘移到B上，再把下面的圆盘移到C上，最后把B上的圆盘移到C上，到此转移完毕

。

移动次数？一般地：2023/2/4组合数学139

假定n-1个盘子的转移算法已经确定。先把上面的n-1个圆盘经过C转移到B，第二步把A下面一个圆盘移到C上，最后再把B上的n-1个圆盘经过A转移到C上

。

上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，…以此类推。

2023/2/4组合数学140算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。

n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有算法复杂度为：h(n)是n的指数函数，若n=60,260≈1.15292×1018，以一秒移动一个圆盘的速度，则要移动60个圆盘的Hanoi塔，需要2023/2/4组合数学141[例]10个数字(0到9)和4个四则运算符(+,－,×,÷)组成的14个元素。求由其中