组合数学课件

12.7一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨，如果每次从袋子里取出1个水果，那么至少取出多少次后能够保证已经拿出10个相同种类的水果。解：设a1,a2,a3和a4分别为取出四种水果的个数，令r=10，由鸽巢原理加强形式推论2，知要使a1，a2，a3，a4至少有一个不小于r，则 （a1+a2+a3+a4）/4>r-1=10-1可得：a1+a2+a3+a4>36，即当至少取37个水果时，可保证已经拿出10个相同种类的水果。鸽巢原理22.10证明：在任意选取的n+2个正整数中存在两个正整数，其差或和能被2n整除。证明：设a1，a2…an+2为任取n+2个正整数，考虑这n+2个正整数除以2n的余数，其余数只能为0,1,…,2n-1。将余数分为{0}、{1，2n-1}、{2，2n-2}…{n}这n+1个组，则由鸽巢原理知，n+2个正整数中至少有两个数除以2n的余数，落入同一组内。

若这个数的余数落入{0}、{n}组内，则其差和其和均能被2n整除，若余数落入其他组内，余数若相同，则可知其差能被2n整除，若余数不同，则其和能被2n整除。鸽巢原理32.12某学生有37天的时间准备考试，根据她过去的经验至多需要复习60个小时，但每天至少复习1小时。证明无论怎样安排都存在连续的若干天，使得她在这些天里恰好复习了13小时。证明：设ai是从第1天到第i天复习的小时数，i=1,2,…,37。因为每天至少复习1小时，所以

1≤a1<a2<…<a37。又因为至多需要复习60小时，因此a37≤60。

1≤a1<a2<…<a37≤60

。做序列：a1+13,a2+13,…,a37+13,

这个序列也是严格单调上升的，且有a37+13≤73。

14≤a1+13<a2+13

<…<a37+13

≤73

考察序列：a1,a2,…,a37,a1+13,a2+13,…,a37+13,该序列有74个数，每个数都是小于等于73的正整数，由鸽巢原理必存在i和j,使得ai=

aj+13(j<i)。令n=i-j,则该学生在第j+1,j+2,…,j+n=i的连续n天中复习了13小时。鸽巢原理4证明：任取三个连续的扇形，由它们构成一组扇形组合，则圆盘上可取36个不同的扇形组合。这36个扇形组合上数字之和共为：

3*36*（36+1）

3*（1+2+…+36）=2则每个扇形组合上数字之和的平均值为：

3*36*（36+1）

=55.5>56-12*36由定理2.2.1的推论2，必存在三个连续的扇形，其中的数字之和至少是56.2.14把一个圆盘分成36个相等的扇形，然后把1,2,…,36这些数任意填入36个扇形中，证明存在三个连续的扇形，其中的数字之和至少是56。鸽巢原理53.2比5400大的四位整数中，数字2和7不出现，且各位数字不同的整数有多少个？解：分成两种情况考虑：

①若千位为5,则百位可取4,6,8,9，十位可取非2、7以及千位和百位上的数，即P(6,1)，同样取个位数的方案为P(5,1)，则由乘法原则知N1=P(4,1)*P(6,1)*P(5,1)=120。

②若千位不为5，则可取6,8,9，百位可取非2,7和千位上的数，即P(7,1),同样,十位和个位上取数方案分别为P(6,1)和P(5,1),则由乘法原则知 N2=P(3,1)*P(7,1)*P(6,1)*P(5,1)=630。则加法原则可得：

N=N1+N2=750基本计数原理6加法原则与乘法原则3.312个人围坐在圆桌旁，其中一个拒绝与另一个相邻，问有多少种安排方法？

解:(1)若这两人是确定的：先把其他11个人安排在圆桌旁，共有11!/11种；固定这11人后再把剩下的那个人加以安排，他的位置共9个，所以总的排法为11!/11×9=9×10!（种）.（2）如果这两个人是任意的：先选出这样两个人来，有C(12,2)种选法；确定这两个人后，排法有11!/11×9种。故总的排法有:C(12,2)×11!/11×9=54×11!（种）.73.4有颜色不同的四盏灯。(1)把它们按不同的次序全部挂在灯杆上表示信号，共有多少种不同的信号？(2)每次使用一盏、二盏、三盏和四盏灯按一定的次序挂在灯杆上表示信号，共有多少种不同的信号？(3)在(2)中，如果信号与灯的次序不关，共有多少种不同的信号？解:(1)为全排列问题，有P(4,4)=24种。

(2)N=C(4,1)*P(1,1)+C(4,2)*P(2,2)+C(4,3)*P(3,3)+C(4,4)*P(4,4)=4+12+24+24=64种。

(3)N=C(4,1)+C(4,2)+C(4,3)+C(4,4)=4+6+4+1=15种。加法原则与乘法原则8排列与组合3.4

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

（1）P(4,4)=24

（2）P(4,1)+P(4,2)+P(4,3)+P(4,4)=6493.10试求不定方程x1+x2+…+x8=40满足xi≥i(i=1,2,…,8)的整数解的个数？解：令yi=xi–

i，因xi≥i，则yi≥0，不定方程转化为：

(1+y1)+(2+y2)+…+(8+y8)=40 y1+y2+…+y8=40–(1+8)*8/2=4则不定方程y1+y2+…+y8=4满足yi

≥0的整数解的个数即为所求。由定理3.2.4证明可知，该方程的非负整数解个数等于集合{7.0,4.1}的全排列，因此所求不定方程x1+x2+…+x8=40满足xi≥i(i=1,2,…,8)的整数解的个数为：=330排列与组合10

解：先考虑对角线下方的路径，这种路径都是从(0,0)点出发经过(1,0)点及(n,n-1)点到达(n,n)点的。可以把它看作是从(1,0)点出发到达(n,n-1)点的不穿过对角线的非降路径。从(1,0)点到(n,n-1)点的所有非降路径数是3.13计数从(0,0)点到(n,n)点不穿过直线y=x的非降路径数。y=x+1Ay=x(-1,2)(1,0)(0,1)(0,0)xy(n,n)(n,n-1)非降路径问题11

对其中任意一条穿过对角线的路径，可以看成从(1,0)点出发到(n,n-1)点的接触直线y=x+1的所有非降路径，把这样的一条路径的(1,0)点到其最后离开y=x+1的点A部分按照直线y=x+1作一个反射，就得到一条从(-1,2)到达y=x+1Ay=x(-1,2)(1,0)(0,1)(0,0)xy(n,n)(n,n-1)(n,n-1)的非降路径，反之，任何一条从(-1,2)出发到(n,n-1)点的非降路径也可以通过这种反射对应到一条从(0,1)到达(n,n-1)点并接触y=x+1的非降路径。从(-1,2)到达(n,n-1)点的非降路径数为：非降路径问题12，由对称性可知，所求的路径数是：，从而在对角线下方的路径数是非降路径问题13非降路径问题14非降路径问题15非降路径问题16非降路径问题n越过和接触y=x越过（不包括接触）y=x1002423161017nmr0n-1m-1r+11++…+n-m0r+mm=n+r+1m证明：表示从(0,0)点到(n+r+1-m,m)点的非降路径数，任何这样的路径一定经过图中x=r线上的点，把它们按经过直线上的不同的点向右而分类。从(0,0)到(r,k)点的非降路径是条。n+r+1mr+kk(0,0)xy(n+r+1-m,m)x=r…(r,k)(r+1,k)从(r,k)到(r+1,k)的非降路径是1条。从(r+1,k)到(n+r+1-m,m)的非降路径是条，由乘法法则，从(0,0)点经(r,k)和(r+1,k)到(n+r+1-m,m)点的非降路径是条，再对k=0,1,…m求和就得到所有从点(0,0)到点(n+r+1-m,m)的非降路径数，等式得证。n-km-kr+kkn-km-k3.28用非降路径的方法证明以下组合恒等式：183.35用多项式定理展开解：=其中求和是对满足方程的一切非负整数解来求。多项式系数19容斥原理20容斥原理21容斥原理习题4.11与1000之间不能被4,5和6整除的整数有多少个？解:

令A={1,2,3,…,1000}，则

|A|=1000.记A1、A2、A3分别为在1与1000之间能被4,5和6整除的整数集合，则有：|A1|=L1000/4」=250,

|A2|=L1000/5」=200,|A3|=L1000/6」=166,于是A1∩A2表示A中能被5和6整除的数,即能被30整除的数，其个数为

|A1∩A2|=L1000/20」=50；22容斥原理同理,|A1∩A3|=L1000/12」=83,|A2∩A3|=L1000/30」=33,A1∩A2∩

A3

表示A中能同时被4,5,6整除的数，即A中能被4,5,6的最小公倍数lcm(4,5,6)=60整除的数，其个数为

|A1∩A2∩A3|=L1000/60」=16.由容斥原理知，A中不能被4，5，6整除的整数个数为:=|A|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A3∩A2|)-|A1∩A2∩A3|=53423容斥原理24容斥原理25容斥原理26容斥原理27解：令S’

={

}，S’的所有的9-组合构成集合W，则可得：

4.4求S=｛｝的9-组合数容斥原理

任取S’的一个9-组合，如果其中的b多于3个，则称它具有性质p1;如果其中c多于5个，则称它具有性质p2;如果其中d多于7个，则称它具有性质p3。不难看出所求的9-组合数就是W中不具有性质p1，p2和p3的元素个数。

Ai=｛ｘ∣ｘ∈Ｗ∧ｘ具有性质pi}i=1,2,3,4计算|A1|、|A2|和|A3|：A1中的每个9－组合至少含有4个b，把这4个b拿走就得到S’的一个5－组合。反之，对T的任意一个5－组合加上4个b就得到中的一个9－组合。所以就是S’的6－组合数，即28用类似的方法可以计算|A1∩A2|

、|A1∩A3|

、|A2∩A3|

和|A1∩A2∩A3

|

则所求9-组合：=220-（56+20+4）=140容斥原理294.9求多重集S={4·a,2·b,3·c}的排列数，要求排列中的同类字母的全体不能相邻。解：多重集S={4·a,2·b,3·c}的全排列要构成集合W，则其全排列数为任取S的一个全排列，如果其中字母a的全体相邻，则称它具有性质p1;如果其中字母b的全体相邻，则称它具有性质p2;如果其中字母c的全体相邻，则称它具有性质p3。

Ai=｛ｘ∣ｘ∈Ｗ∧ｘ具有性质pi}i=1,2,3计算|A1|。

A1中4个a全体相邻，则将其作为一个整体a’与其它字母排列，为{1·a’,2·b,3·c}全排列，故容斥原理30类似可计算|A2|、|A3|、|A1∩A2|

、|A1∩A3|

、|A2∩A3|

和|A1∩A2∩A3

|。=1260-（60+280+105）+（20+12+30）-6=871则所求为：容斥原理314.10从一个4×4的棋盘中选取2个方格，使得它们不在同一行也不在同一列，共有多少种选法？解：在4×4的棋盘中共有16个方格，因此第1个方格的选取的方案数为16，第二方格要与第一个方格不在同一行也不在同一列，因此只能选择去除第1个方格所在行和列的3×3=9个方格中的一个，故可选方案数为9，而第1个方格与第2个方格与选择顺序无关，故所求的方案数为：

16*9/2=72。容斥原理32思考题：从一个m×m的棋盘中选取n(n≤m)个方格，使得它们不在同一行也不在同一列，共有多少种选法？解：(P(m,n))2/n!容斥原理33容斥原理R()=x·R()+R() =x(1+2x)+(1+3x) =1+4x+2x2R()=x·R()+R() =x·1+x()+() =x+x(1+x)+(1+x)2=1+4x+2x234容斥原理R()=x·R()+R()=x·[x·R()+R()]+[x·R()+R()]=x[x(1+x)+(1+2x)]+[x(1+2x)+(1+4x+2x2)]=1+6x+7x2+x335容斥原理R()=x·R()+R()=x(1+x)+x·R()+R()=x(1+x)+x(1+2x)+x·R()+R()=x(1+x)+x(1+2x)+x(1+x)+(1+x)3=1+6x+7x2+x336组合数的生成函数37组合数的生成函数38排列数的指数型生成函数39生成函数在计数问题中的应用习题5.3由a,b,c,d,e组成的长为n的字中,要求a与b

的个解

分两种情况:

数之和为偶数,问这样的字有多少个?（1）a与b的个数都为奇数;则对第一种情况有

（2）

a与b的个数都为偶数;

该排列的指数型生成函数为

40生成函数在计数问题中的应用对第二种情况有

所以

的系数为

该排列的指数型生成函数为

故这样的字的个数有

所以

的系数为

41生成函数在计数问题中的应用42生成函数在计数问题中的应用习题5.4证明方程

有相同数目的非负和

整数解.

不同的盒子里放13个相同的球,则各盒子可装的球的个数为可以看成是在7个证明

方程

{0,1,2,…,13}个.用生成函数表示为43生成函数在计数问题中的应用当时,的系数为

.在这里,k=13,故其系数为

44生成函数在计数问题中的应用不同的盒子里放14个相同的球,则各盒子可装的球的个数可以看成是在6个同理方程

为{0,1,2,…,6}个.用生成函数表示为当时,的系数为

.在这里,k=6,故的.因此得证.

系数为

45生成函数在计数问题中的应用习题5.4证明方程

有相同数目的非负整数解和

不同的盒子里放13个相同的球,则各盒子可装的球的个数为可以看成是在7个证明

方程

{0,1,2,…}个.用生成函数表示为当时,的系数为

.在这里,k=13,故其系数为

46生成函数在计数问题中的应用不同的盒子里放14个相同的球,则各盒子可装的球的个数可以看成是在6个同理方程

为{0,1,2,…,6}个.用生成函数表示为当时,的系数为

.在这里,k=6,故的.因此得证.

系数为

47排列数的指数型生成函数48排列数的指数型生成函数49排列数的指数型生成函数50排列数的指数型生成函数51排列数的指数型生成函数52排列数的指数型生成函数53生成函数54递推关系55递推关系56递推关系57递推关系58递推关系59递推关系60递推关系61递推关系62递推关系63递推关系64递推关系65递推关系66递推关系67递推关系68递推关系69递推关系70递推关系71生成函数72基本计数原理3.78个棋子大小相同，其中5个红的，3个蓝的。把它们放在8×8的棋盘上，每得、每行、每列只放一个，问有多少种放法？若放在12×12的棋盘上，结果如何？1.先放红色的.（1）在8行中任选5行放红色棋子，有C（8,5）种选择.（2）选定行后，再选列.因为每行都不同，故有P（8,5）种选择.现在再放蓝色的棋子.还剩3行、3列，而每个棋子都是相同的，故可把第一个棋子放在剩下的第一行，3列可选;第二个棋子放第二行，2列可选；第三个棋子则只剩下1行1列可选.于是，有3!种方案.根据乘法原理，共有C（8,5）×P（8,5）×3!=种放法.73基本计数原理74基本计数原理75基本计数原理3.18将52张牌平均分给4个人，问每人有一个5张牌的同花顺的概率是多少？解首先分给4个人每人一个5张牌的同花顺的个数：(1)4个人每人的5张同花顺颜色均不同.每一种花色均有9种不同的同花顺.故共有P（4,4）×94种可能.(2)4个人中有两人是同色的同花