组合数学第一章答案.

１.１从5021，，，中找两个数ba,，使其满足（1）5||ba；（2）5||ba解：（1）根据5||ba可得55baba或则有种种4545共有90种。（2）根据5||ba得)50,,2,1(,55{babab则：当5b时，有1b，61a，则有6种2b，71a，则有7种3b，81a，则有8种4b，91a，则有9种5b，101a，则有10种当455b时，有6b，111a，则有11种7b，122a，则有11种.........45b，5040a，则有11种当5045b时，有46b，5041a，则有10种47b，5042a，则有9种48b，5043a，则有8种49b，5044a，则有7种50b，5045a，则有6种故：共种520)678910(211401.2（1）先把女生进行排列，方案为5！，然后把女生看成1个人和7个男生进行排列，总方案数为5！×8！（2）女生不相邻，则先把男生进行排列，方案为7！再把女生插入男生之间的8个空位种的任意5个，总方案数为7！×58P（3）应该是A女生x女生y女生zB,或是B女生x女生y女生zA的形式，从5个女生中选出3人进行排列，方案为35P，考虑A,B可以换位，方案为2×35P，然后把这个看成一个整体，和剩下的2个女生，5个男生，一共7个人进行排列，总方案数2×35P×8！1.3m个男生,n个女生,排成一行,其中m,n都是正整数,若（a）男生不相邻（m≤n+1）；（b）n个女生形成一个整体；（c）男生A和女生B排在一起；分别讨论有多少种方案。解：(a)n!p(n+1,m)(b)(m+1)!n!(c)2(m+n-1)!1．426个英文字母进行排列，求X和Y之间有五个字母的排列数？解:排列数为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个所以综上所述，符合条件的数，根据加法原理共有：672+840=1512个1.61*1!+2*2!+3*3!…………+(n-1)*(n-1)!根据公式得1*1!+2*2!+3*3!…………+(n-1)*(n-1)!=n!-11.7试证（n+1）(n+2)…(2n)被k2除尽。证明：3)...32)(12(2...)!2()!32)(12(2)!2)(1()!32)(12)(22(2)!1()!12(2)!1()!12(2!)!2()2)...(2)(1(2nnnnnnnnnnnnnnnnnnnnnn所以（n+1）(n+2)…(2n)能被k2除尽。1.8求1040和2030的共因数的数目.解:1040=240*5402030=260*530∴1040和2030的公因子有40*30=1200个1.9试证n的平方的正除数的数目是奇数答案：因为n的平方一定是两个数的乘积，一定是两个不同的数的乘积或唯一的一个相同的数的乘积。例如，16可以是1*16，2*8或4*4，前面的都是成对出现的，只有4是一个数，所以他们的和一定是奇数。1.10证明任一正整数n可唯一地表示成如下形式：n=1!iiai,0iai,1i证明：对n用数学归纳法①当n=0,1时，0=01!,1=11!。命题成立。②假设对于小于n的非负整数，命题成立。③对于n，设!(1)!knk，即0!(1)!!(11)!!nkkkkkkk由②，对!nk命题成立。设1!!kiinkai，其中0iai，01kak(原因是0!!nkkk而不能等于!kk)，那么111!!!(1)!kkiikiinaikaiak，其中01kak，命题成立。再证唯一性：设11!!kkiiiinaibi，不妨设jjab，min{|}iijiab，即1231231!2!3!1!2!3!aaabbb，假设11ab，22ab，33ab，则j=3。那么，因为ia与ib前j项相等，上式两边均减去前j项，即!!iiijijaibi，即1212!(1)!(2)!!(1)!(2)!jjjjjjajajajbjbjbj将上式两边都除以(1)!j，得1212!!(2)(2)(1)!(1)!jjjjjjajbjaajbbjjj可以看出，上式的余数为!jaj=!jbj与假设矛盾。因此ia是唯一的1.11求证：nC(n-1,r)=(r+1)C(n,r+1)证明：左边=C(n,1)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)=左边所以等式成立。1—12试证:nknnknkC112),(证明:(1+x)n=C(n,0)+C(n,1)x+C(n,2)x2+…+C(n,n)xn两边求导,并令x=1代入n(1+1)1n=C(n,1)+C(n,2)x+C(n,3)x2+…+C(n,n)x1nn2nknknkC11),(组合意义:设有n个不同的小球,A,B两个盒子,A盒中恰好放1个球,B盒中可放任意个球.有两种方法放球:第一种:先从n个球中取k个球(k≥1),在从k中挑一个放入A盒,方案数共为nkknkC1),(,其余放入B盒.第二种:先从n个球中任取一球放入A盒,剩下n-1个球每个球有两种可能,要么放入B盒,要么不放,故方案数为n21n,显然相等.1.13：有N个不同的整数，从中取出两组来，要求第一组的最小数大于第二组的最大数。解：本题求取两组数的取法。我们首先从N中去M个数（2=M=N）,因为M个数是不同的，所以存在一个递增的序列A=a1,a2,a3,a4……aM(a1a2a3a4……aM)。然后我们从序列Ａ中按顺序取出｛a1｝，｛a1,a2｝，｛a1,a2,a3｝．．．．．｛a1,a2,a3,a4……aM－１｝作为第一组，剩下的作为第二组。就可以保证第一组的最小数大于第二组的最大数。从N中去M，共有C（n，m）种，每一种M对应一个序列A，每一个序列A对应M-1种分组方法。所以对于每一个M共有，C（n，m）×（m-1）种分组方法。又因为2=M=N，所以总共的分组方法为：1.146个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从一个特定引擎开始有多少方案？解：设6个引擎分别为1、2、3、4、5、6不失一般性，我们把1、2、3放在第一排，4、5、6放到第二排。由题意知从一个特定引擎开始，不妨设从1开始，那么（1）1开启之后，下一个开始点有4、5、6三种选择（2）第二排的一个开启之后，下一个开始点有2，3两种选择（3）然后第一排，第二排剩下俩，那么有两种选择（4）然后第一排只剩一个，第二排只剩一个，所以就剩一种选择所以，由乘法法则方案数=3×2×2×1×1=121.15试求从1到1000000的整数中，0出现了多少次？解：先考虑1到999999.个位为零的整数出现99999×1次为：10—999990十位为零的整数出现9999×10次为：101—999909百位为零的整数出现999×100次为：1000—999099千位为零的整数出现99×1000次为：10000—990999万位为零的整数出现9×10000次为：100000—909999而1000000本身有6个零所以从1到1000000的整数中，0出现的次数为：99999×1+9999×10+999×100+99×1000+9×10000+6=4888951.16n个完全一样的球放在r个有标志的盒子里面rn，无一空盒，问有多少种方案？解：r个盒子无一空盒，说明先要从n个球中取出r个先放每个盒中一个；余下n-r个无标志的球，放入r个有标志的盒子中，根据定理可以得出结果是rnnCrnrnrC,1,1。1.17n和r都是正整数，而且rn，试证下列等式1)11nnrrpnp2)1(1)nnrrpnrp3)1,nnrrnpprnnr4)11nnnrrrpprp5)1111!(nnnrrrprrpp……1)rrp1）证明：左边=n*(n-1)……（n-r+1）右边=n*(n-1)……（n-r+1）所以左边=右边同理：（2）（3）（4）得证。5）证明：利用（4），11nnnrrrpprp=11111111()()nnnnnnrrrrrrprprpprpp……=等式右边1．188个盒子排成一列，5个有标志的球放到盒子中，每个盒子最多放一个球，要求空盒子不相邻，问有多少种排列方案。解：P(5,5)*C(6,3)=2400（种）答：共有2400种方案。1.19．n+m位由m个0，n个1组成的符号串，其中nm+1，试问不存在两个1相邻的符号串的数目。解：该题可以看作是往m个0里插入n个1，即从m+1个空中选取n个空放1，这样就使得不存在两个1相邻，总的解决方案数为：(1,)Cmn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）14175021011504410CCCC，（2）50400011021514310CCCC，（3）12285001031524210CCCC。因此，符合条件的方案数共有：141750+504000+122850=768600种。1.21一个盒子里有7个无区别的白球，5个无区别的黑球。每次从中随机取走一球，已知前面取走6个，其中3个是白的。试问第6个球是白球的概率？解：设6个球的编号分别为1、2……6。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）353253560CC（2）343243350CC（3）312323122240CCC（4）534583243937CCC1.23令{1,2,.......,1},2,{(,,)|,,,,}snnTxyzxyzsxzyz，试证：2111323nknnTk解题：（1）：因为x,y的最小值为1，所以(2,3,4,........)zn当z=2时：x=y=1,当z=3时：x,y各有两种选择1122CC………当z=n+1时：x,y各有两种选择11nnCC即：21nkTk（2）：因为,,xyzs且,xzyz。当x=y时，从(1,2,......1)n取两个数，大的给z，小的给x,y,有21nC。当xy时，(1,2,.....