组合数学卢开澄版答案第一章

1、.从中找两个数，使其满足（1） ；（2）解：（1）根据 可得 则有 共有90种。（2）根据 得 则：当时，有 ， ， 则有 6种 ， ， 则有7种 ， ， 则有8种 ， ， 则有 9种 ， ， 则有10种当时，有 ， ， 则有 11种 ， ， 则有 11种 . . . . . . . . . ， ， 则有11种当时，有 ， ， 则有 10种 ， ， 则有 9种 ， ， 则有 8种 ， ， 则有 7种 ， ， 则有 6种故：共 1.2 （1）先把女生进行排列，方案为5！，然后把女生看成1个人和7个男生进行排列，总方案数为5！8！（2）女生不相邻，则先把男生进行排列，方案为7！再把女生插入男生之间

2、的8个空位种的任意5个，总方案数为7！（3）应该是A 女生x 女生y 女生z B,或是B女生x 女生y 女生z A的形式，从5个女生中选出3人进行排列，方案为，考虑A,B可以换位，方案为2，然后把这个看成一个整体，和剩下的2个女生，5个男生，一共7个人进行排列，总方案数28！1.3 m个男生,n个女生,排成一行,其中m,n都是正整数,若（a）男生不相邻（mn+1）；（b）n个女生形成一个整体；（c）男生A和女生B排在一起；分别讨论有多少种方案。 解：(a)n!p(n+1,m)(b)(m+1)!n!(c)2(m+n-1)!14 26个英文字母进行排列，求X和Y之间有五个字母的排列数？解:排列数为

3、C(24,5)*5！*2*20！1.5 求3000到8000之间的奇整数的数目，且没有相同的数字。解：设四位数为n3n2n1n0.由已知可知，n3只能取，3，4，5，6，7，8，n0只能取1,3,5,7,9.分以下两种情况讨论：1.当n3取3，5，7的时候，由于是不能重复的，所以n0只能有4种选择，而剩下的n2,n1分别有8，7种选择。所以符合条件的数，根据乘法原理有：3*4*8*7=672.个 2.当n3取4，6，8时，由于是不能重复的,所以n0有5种选择，而剩下的n2,n1分别有8，7种选择，所以符合条件的数，根据乘法原理有： 3*5*8*7=840个 所以综上所述，符合条件的数，根据加法

4、原理共有： 672+840=1512个1.6 1*1!+2*2!+3*3!+(n-1)*(n-1)! 根据公式得 1*1!+2*2!+3*3!+(n-1)*(n-1)!=n!-1试证 （n+1）(n+2)(2n)被除尽。证明：所以（n+1）(n+2)(2n)能被除尽。1.8 求1040和2030的共因数的数目. 解: 10 40=2 40 * 5 40 20 30=260 * 5 30 1040和2030的公因子有40*30=1200 个1.9 试证n的平方的正除数的数目是奇数答案：因为n的平方一定是两个数的乘积，一定是两个不同的数的乘积或唯一的一个相同的 数的乘积。例如，16可以是1*16，

5、2*8或4*4，前面的都是成对出现的，只有4是一个 数，所以他们的和一定是奇数。1.10 证明任一正整数n可唯一地表示成如下形式： n=, , 证明：对n用数学归纳法 当n=0,1时，0=01! , 1=11!。命题成立。 假设对于小于n的非负整数，命题成立。 对于n，设，即由，对命题成立。设，其中， (原因是而不能等于)，那么，其中，命题成立。再证唯一性：设，不妨设，即，假设，则j=3。那么，因为与前j项相等，上式两边均减去前j项，即，即 将上式两边都除以，得 可以看出，上式的余数为=与假设矛盾。因此是唯一的1.11求证：nC(n-1,r)=(r+1)C(n,r+1)证明：左边=C(n,1)

6、C(n-1,r)右边=C(r+1,1)C(n,r+1)=C(n,1)C(n-1,r+1-1)=C(n,1)C(n-1,r)=左边所以等式成立。112 试证: 证明: (1+x) =C(n,0)+C(n,1)x+C(n,2)x+C(n,n)x 两边求导,并令x=1代入n(1+1)=C(n,1)+C(n,2)x+C(n,3)x+ +C(n,n)xn2组合意义: 设有n个不同的小球,A,B两个盒子,A盒中恰好放1个球,B盒中可放任意个球.有两种方法放球:第一种: 先从n个球中取k个球(k1),在从k中挑一个放入A盒,方案数共为,其余放入B盒.第二种: 先从n个球中任取一球放入A盒,剩下n-1个球每个

7、球有两种可能,要么放入B盒,要么不放,故方案数为n2, 显然相等.1.13：有N个不同的整数，从中取出两组来，要求第一组的最小数大于第二组的最大数。解：本题求取两组数的取法。我们首先从N中去M个数（2=M=N）,因为M个数是不同的，所以存在一个递增的序列A=a1,a2,a3,a4aM (a1a2a3a4aM)。 然后我们从序列中按顺序取出a1，a1,a2，a1,a2,a3a1,a2,a3,a4aM作为第一组，剩下的作为第二组。就可以保证第一组的最小数大于第二组的最大数。从N中去M，共有C（n，m）种，每一种M对应一个序列A，每一个序列A对应M-1种分组方法。所以对于每一个M共有，C（n，m）（

8、m-1）种分组方法。又因为2=M=N，所以总共的分组方法为：m=2nCn，mm-11.14 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从一个特定引擎开始有多少方案？ 解： 设6个引擎分别为1、2、3、4、5、6 不失一般性，我们把1、2、3放在第一排，4、5、6放到第二排。 由题意知从一个特定引擎开始，不妨设从1开始，那么（1）1开启之后，下一个开始点有4、5、6三种选择（2）第二排的一个开启之后，下一个开始点有2，3两种选择（3）然后第一排，第二排剩下俩，那么有两种选择（4）然后第一排只剩一个，第二排只剩一个，所以就剩一种选择 所以，由乘法法则方案数=32211=121.15试求

9、从1到1000000的整数中，0出现了多少次？解：先考虑1到99 9999.个位为零的整数出现999991次 为：10999990十位为零的整数出现999910次 为：101999909百位为零的整数出现999100次 为：1000999099千位为零的整数出现991000次 为：10000990999万位为零的整数出现910000次 为：100000909999而100 0000本身有6个零所以从1到1000000的整数中，0出现的次数为：999991+999910+999100+991000+910000+6=4888951.16 n个完全一样的球放在r个有标志的盒子里面 ，无一空盒，问有

10、多少种方案？ 解：r个盒子无一空盒，说明先要从n个球中取出r个先放每个盒中一个； 余下n-r个无标志的球，放入r个有标志的盒子中，根据定理可以得出 结果是 。1.17 n和r都是正整数，而且rn，试证下列等式 1） 证明：左边=n*(n-1)（n-r+1） 右边= n*(n-1)（n-r+1）所以 左边=右边同理：（2）（3）（4）得证。5）证明：利用（4）， =等式右边118 8个盒子排成一列，5个有标志的球放到盒子中，每个盒子最多放一个球，要求空盒子不相邻，问有多少种排列方案。 解： P( 5 , 5 )*C( 6 , 3)=2400（种）答：共有2400种方案。1.19n + m 位由m

11、个0，n个1组成的符号串，其中nm+1，试问不存在两个1相邻的符号串的数目。解：该题可以看作是往m个0里插入n 个1，即从m+1个空中选取n个空放1，这样就使得不存在两个1相邻，总的解决方案数为：1.20 甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志5位，试问有多少种方案？ 解： 根据题意，符合要求的组合法有3种：（1）甲单位4男0女，乙单位1男2女；（2）甲单位3男1女，乙单位2男1女；（3）甲单位2男2女，乙单位3男0女。则对应的组合数为：（1），（2）， （3）。因此，符合条件的方案数共有：141

12、750+504000+122850=768600种。1.21 一个盒子里有7个无区别的白球，5个无区别的黑球。每次从中随机取走一球，已知前面取走6个，其中3个是白的。试问第6个球是白球的概率？解：设6个球的编号分别为1、26。6个球中第6个球是白球的所有可能方案为：126、136、146、156、236、246、256、346、356、456，既有10种可能。那么第6个球是白球的概率为10/C（6，3）=1/2。1.22 求图1-22中从0到P的路径数。（1）路径必须经过A点（2）路径必须过道路AB（3）路径必须过A点和C点（4）道路AB封锁（但A,B两点开放）解题：（1） （2） （3） （

13、4）1.23 令，试证：解题：（1）：因为x,y的最小值为1，所以 当z=2时：x=y=1, 当z=3时：x,y各有两种选择 当z=n+1时：x,y各有两种选择即： （2）：因为且。当x=y时，从取两个数，大的给z，小的给x,y,有。当时，取三个数，大的给z，小的给x或y，有，即：A=(a,b)|a,bZ,0a9,0b5求x-y平面上以A作顶点的长方行数目；求x-y平面上以A作顶点的正方形数目；如图所示132450678912345解：思想是分别以纵坐标0、1、2、3、4为起点，横坐标和纵坐标一起够成的长方形即：4*C（9，1）+4*C（9，2）+4*C（9，3）+4*C（9，4）+4*C（9

14、，5）+5*C（9，6）+5*C（9，7）+5*C（9，8）+5 + 3*C（9，1）+3*C（9，2）+3*C（9，3）+3*C（9，4）+4*C（9，5）+4*C（9，6）+4*C（9，7）+4*C（9，8）+4 + 2*C（9，1）+2*C（9，2）+2*C（9，3）+3*C（9，4）+3*C（9，5）+3*C（9，6）+3*C（9，7）+3*C（9，8）+3+ C（9，1）+C（9，2）+C（9，3）+C（9，4）+C（9，5）+C（9，6）+C（9，7）+C（9，8）+1=13374即以A作顶点的长方形数目为13374个。同理以A作顶点的正方形数目为：C（9，1）+C（9，2）+C（

15、9，3）+C（9，4）+C（9，5）+C（9，1）+C（9，2）+C（9，3）+C（9，4）+C（9，1）+C（9，2）+C（9，3）+C（9，1）+C（9，2）+C（9，1）=1071即以A作顶点的正方形数目为1071个。平面上有15个点，P1，P2，P15，其中P1，P2，P3，P4，P5共线，此外不存在3点共线的。（a）求至少过15个点中两点的直线的数目；（b）求由15个点中3点组成的三角形的数目。 解：（a）根据题意，符合条件的直线有三种可能：（1）P1，P2，P3，P4，P5构成的直线，有1条；（2）P6P15中的任选两点构成的直线，有条；（3）由P1P5中的一个点及P6P15中的一

16、个点构成的直线，有条。因此，符合要求的直线共有1+45+50=96条。（b）根据题意，符合条件的三角形有三种可能：（1）P1P5中任选两个点及P6P15中任选一个点构成三角形：有个；（2）P1P5中任选一个点及P6P15中任选两个点构成三角形：有个；（3）P6P15中任选三个点构成三角形：有个。因此，共可组成三角形100+225+120=445个。1.26。 解：由题知，说明a*b能被5整除。则分为两种情况： a ,b 同时为5的倍数 1000中5的倍数有200个 方案数为：200*199/2 a ,b 不同时为5的倍数，即a ,b中有一个不是5的倍数 方案数为：800*200总的总的方案数为

17、：200*199/2+800*2006位男宾，5位女宾围一圆桌而坐，女宾不相邻有多少种方案。所有女宾在一起有多少种方案。一女宾A和两位男宾相邻又有多少种方案。解：（1）5！*P( 6 , 5 )=120*720 =86400 答：女宾不相邻有86400种方案。 （2）6！*5！=86400答：所有女宾在一起有86400种方案 （3）8！*2*C（6 ，2）=40320*2*3*5=1209600答：一女宾A和两位男宾相邻又有1209600种方案。1.28 k和n都是正整数，kn位来宾围着k张圆桌而坐，试求方案数。解; 方案数为：C(nk,n)*(n-1)!* C(n(k-1),n)*(n-1)

18、! * C(n(k-2),n)*(n-1)!* C(n,n)*(n-1)!整理得：(n-1)!k * C(nk,n)* C(n(k-1),n)*C(n,n)= (n-1)!k *(nk)!/ (n!) k=(nk)!/ n k 1.29 从n个对象中取r个作圆周排列，求其方案数？ 解：！1.30试证下列等式 证明：（1） （2） （3）1.31 试证明任意r个相临数的连乘： 被r！除尽 解： 显而易见，是一个整数，由= 由于是整数，所以是整数，那么可以被r！除尽1.32： 在 a,b,c,d,e,f,x,x,x,y,y 的排列中，要求y必须夹在两个X之间，问这样的排列数等于多少？解：要求y必须

19、在两个x之间，所以符合要求的排列必须有结构“xyxyx”，把“xyxyx”看作一个元素，与a,b,c,d,e,f,排列排列数等于6！。133 已知r,n,k都是正整数,rnk,将r个无区别的球放在n个有标志的盒子里,每盒至少k个球,试问有多少种方案?解: 先保证每一个盒子至少k个球,因为球无区别,把n个不同盒子每一个盒子放k个球.共kn个.问题转化为将(r-nk)个小球放入n个不同盒子,每个盒子可以放任意个球,可以有空盒,根据可从复组合定理可得共(n+r-nk-1,r-nk)=(n+r-nk-1,n-1)1.34在r，s，t，u，v，w，x，y，z，的排列中求y居于x和z中间的排列数。解：一共

20、9个位置，y只能放到2到8中间，当x放到第一个位置，y放到第二个位置，其他全排列有7！种方法，第一个位置也可以放z，共有2*7！种方法。y放到第三个位置，y前x有两种选择，y后z有6种选择，其他全排列，所以方法有2*6*6！，总方法有2*2*6*6种方法，以此类推算到y在第5个位置因为后边是对称的。总数=2*（7！+2*6*6！+3*5*6！+4*4*6！）=72000135 凸十边形的任意三条对角线不共点。试求这凸十边形的对角线交于多少个点？解： 根据题意，每4个点可得到两条对角线，1个对角线交点，从10个顶点任取4个的方案有C(10,4)种，即交于210个点。1.36 试证明一个整数是另一

21、个整数的平方的必要条件是除尽它的数的数目是奇数。答案：由：n=，其中是质数，是正整数。则n的因子数有(a1+1)(a2+1)(a3+1)个。得 =，因为(2a1+1),(2a2+1),(2a3+1).都是奇数，所以 的因子数为(2a1+1)(2a2+1)(2a3+1).个，也是奇数个。1.37 给出 的组合意义. y 解: A(-1,m) m B(m-n,m) . . . . . . C(-r-1,0) -r-1 -1 0 m-n 可看作是格路问题:左边第i项为从点C到点(-1,i)直接经过(0,i)的路径,再到点B的所有路径。左边所有项的和就是从C点到B点的所有路径数即为右边的意义.1.38

22、 给出的组合意义。解：设，从A中取r+1个元素组合成C，考虑以下n-r+1种情况：（1），则A需从中取r个与配合，构成C，共中可能。（2），则需从中取r个，加上构成C，共种可能。（n-r）,则需从中取r个组合，再加上构成C，共种可能。（n-r+1）,这时只有=1种可能。故1.39证明:证：组合意义,右边：m个球,从中取n个,放入两个盒子,n个球中每个球都有两种放法,得到可能的方案数。左边：第i项的意义是一个盒子中放i个,另一个盒子放n-i个,所有的方案数相加应该等于右边。证毕。1.40 从n个人中选出r个围成一个圆圈，问有多少种不同方案。解：首先从n个人中选出r个有C(n,r)种方案，r个人进

23、行一个圆周排列，根据圆周排列公式，共有r!r种方案，既(r-1)!种方案，所以根据乘法法则，一共有C(n,r)*(r-1)!种方案。1.41 分别写出按照字典序，由给定排列计算其对应序号的算法及由给定序号计算其对应的算法。解：生成所有排列的数组A： S1. A0-12N，LEN=1；S2. j-0;j从0到n，若,则退出；S3. i = max j | ；S4. h = maxk | ；S5.将和 互换的；S6.ALEN- ,LEN+；S7.将和互换，得；S8.ALEN- , LEN+,转到S2;给定排列计算其对应序号的算法S1. 输入；S2.j改为，。转S1。（b）写出按照邻位对换法由给定排

24、列生成其下一个排列的算法。解：S1.Ai1；S2.i从2到n做始Aii，Di i,Ei -1终；S3.q0i从1到n输出Ai;S4.k1则转S6； S6.Dk Dk+Ek,pDk;S7.若p=k则做Ek -1,转S10；S8.若p=0 则做始Ek 1,qq+1转S10终；S9.pp+q，rAp,Ap Ap+1,Ap+1 i，转S3;S10.kn/2时,(n-k+1)/k1,即C(n,k)n/2时,(n-k+1)/k1,即C(n,k)C(n,k-1)得到当k为最接近n/2的数时，C(n,k)取到最大值。1.44 （1）用组合方法证明和都是整数。（2）证明是整数。证明：（1）设有2n个不同的球放入

25、n个不同的盒子里，每个盒子两个，这个方案数应该是整数。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了次，得到的2n个不同球放入n个不同的盒子里，每盒两个的方案数为，得证。同理，若有3n个不同的球，放入n个不同的盒子里，每个盒子3个球，重复的次数为，故方案数为，得证。（2）设有个不同的球，将他们放入n个相同的盒子，每盒n个球，这个方案数应该是整数。由（1）可知，将个不同的球放入n个不同盒子的方案数为，若为相同的n个盒子，则应把n个盒子的排列数去掉，即n！，故个不同的球放入n个相同的盒子，每盒n个球的方案数为，证毕。1.45 （1）在2n个

26、球中，有n个相同，求从这2n个球中选取n个的方案数。（2） 在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数。解：（1）相当于从n个不同的小球中分别取出m个小球（），再从n个不同小球中取出n-m个小球。则共有方案数：（2）相当于从2n+1个不同的小球中分别取出个小球（），再从n个不同小球中取出n-m个小球。则共有方案数：1.46（1）证明：利用归纳法，当n=1时，0出现偶数次的实例是1,2，其中0出现0次，而当n1时，1/2=2，是正确的。 假设当nk时是正确的，即0出现 1/2 次，计算0出现奇数次的方案，因为总方案数为，0出现奇数次的方案为1/21/2. 当nk1时，0出

27、现偶数次的方案数是前k为出现偶数次，第k1位是1或2，或是前k位出现奇数个0，最后一位是0.总方案数为2（1）/21/21/2,正是所要证明的形式，所以0出现偶数次的字符串有1/2个。 （2）证明：等式左边第一项表示n位中有0个0，用表示，那么这n位只能取1或2，有种可能，所以方案为，最后一项为当n中有最大偶数个0出现时的方案数，所以左边整体表示为n位字符串中0出现偶数次的方案数，右边也是0出现偶数次的方案数，左边右边，即证。1.47 5台教学机器m个学生使用，使用第1台和第2台的人数相等，有多少种分配方案？解：当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个

28、使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3(m-2n)。所以总的方案数为.1.48 在由n个0及n个1构成的字符串中，任意前k个字符中，0的个数不少于1的个数的字符串有多少？解：转化为格路问题,即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1).1.49 在1到n的自然数中选取不同且互不相邻的k个数，有多少种方案？解：根据不相邻组合的公式，共有C(n-k+1)种方案k。1.50 (a)在5个0，4个1组成的字符串中，出现01或10的总次数为4的，有多少个?(b)在m个0，n个1组成的字符串中

29、,出现01或10的总次数为k的，有多少个？解：(a)先将5个0排成一列：00000，1若插在两个0中间，“010”，则出现2个“01”或“10”;若插在两端，则出现1个“01”或“10”;要使出现“01”,“10”总次数为4，有两种办法：(1)把两个1插入0得空当内，剩下的1插入1的前面。(2)把1个1插入0得空当内，再取两个1分别插入两端，剩下的1插入1的前面。故总方案数为C(4,2)3+C(4,1)3=30 (b)m个0产生m-1个空当，若k为奇数,则必有且只有1个“1”插入头或尾,总方案数为若k为偶数,总方案数为第一问，出现4个01或10，说明5个0被分成了3段，四个1被分成了两段，然后夹在一起形如001101100；或者5个0被分成了2段，四个1被分成了3段，然后夹在一起形如100100011。于是题目的考虑就变成了5个0如何拆分，4个1如何拆分。答案是：C(4,2)*C(3,1)+C(4,1)*C(3,2)1.51 从中选出3个数，使得没有两个数相邻，问有多少中方案？解：=种从S=1,2,n中选k个数,使之没有两数相邻,求不同方案数.解: 1.53 把n个无区别的球放进有标志1，2，3，n的盒子里，每个盒子里可以放多余一个球，求有多少中方案。答案：相当于在n个不同的元素中取r个作允许重复的的组合，其组