组合数学第三版+卢开澄+习题答案

1、第1章排列与组合经过勘误和调整，已经消除了全部的文字错误，不过仍有以下几个题目暂时没有找到解答：(答案略)(答案略)从1,2,50中找一双数a,b,使其满足:(a) ab5;(b) ab5.解(a)ab5将上式分解，得到ab5ab5a = b方，a=0 时，b = 5, 6, 7, a = b+5, a=5 时，b = 0, 1, 2, ,5Q满足45。满足a=b-5的点共50-4=46个点.a=b+5的点共45-0+1=46个点.所以，共计24692个点.(b)ab5(610)511(454)1651141531个点5个女生，7个男生进行排列，(a)若女生在一起有多少种不同的排列(b)女生两

2、两不相邻有多少种不同的排列(c)两男生A和B之间正好有3个女生的排列是多少解(a)女生在一起当作一个人，先排列，然后将女生重新排列。(7+1)!X5!=8!X5!=40320X120=4838400(b)先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有C；种选择。将女生插入，有5!种方案。故按乘法原理，有：7!XC，X5!=(种)方案。3(c)先从5个女生中选3个女生放入A,B之间，有C；种方案，在让3个女生5个人看作一个人，再与其余7个人一块排列，有排列，有3!种排列，将这(7+1)!=8!由于A,B可交换，如图*A*B*或*B*A*故按乘法原理，有：(种

3、)2XC；X3!X8!=48384001.3m个男生，n个女生，排成一行，其中m,n都是正整数，若(a)男生不相邻(mWn+1)；(b)n个女生形成一个整体；(c)男生A和女生B排在一起；分别讨论有多少种方案.Cm一解(a)先将n个女生排列，有n!种方法，共有n+1个空隙，选出m个空隙，共有Cn1种方法，再插入男生，有m!种方法，按乘法原理，有：m(n1)!n!(n1)!/工、.n!xCn1xm!=n!xxm!=种方案。m!(n1m)!(n1m)!个男生做重排列，然后，n个女生内部n-1+m-1=n+m-2个人一起，作排列, 故有 2X (n+m-1)!种方案。(b)n个女生形成一个整体，看作

4、一个人，与m再作排加，按乘法原理，有(m+1)!xn!种方案。男生A和女生B排在一起，看作一人，和其余共有(n+m-2+1)=(n+m-1)!种方法，A,B两人内部交换,26个英文字母进行排列，要求x和y之间有5个字母的排列数.解选入262=24个字母中选取5个字母，有C24种方法，5个字母内部排列，有5!种方案，再将X*Y这7个字母看作一个，与其余19个合起来作排列，共有(19+1)!=20!种方案，又因为X与Y可交换，故按乘法原理，有：524!24242XC24X5!X20!=2XX5!X20!=40X24!40X/224X5!19!e又因为：ln40+(lg+lg48)+24(lg24T

5、ge)2525=+24所以，结果为e10=x10求3000到8000之间的奇整数的数目，而且没有相同的数字解30008000中各位不同的奇数，分类讨论：首位3,1X8X7X4(末位不能取3)首位4,1X8X7X5(末位全取)首位5,1X8X7X4首位6,1X8X7X5首位7,1X8X7X4从而，由加法原理，得：8X7X(4+5+4+5+4)=56X22=1232个。计算11!22!33!Lnn!n1解11!22!33!nn!(n1)!1(参见p14)(n!1kk!)k1试证(n1)(n2)L(2n)被2n除尽.(2n)!(2n)!(2n1)!2nn!(2n1)!onz证(n1)(n2)(2n)

6、-一-2(2n1)!n!n!n!故能被2n整除。求1040和2030的公因数.解试证n2的正除数的数目是奇数解证明任一正整数n可惟一地表示成如下形式:aii!,(0aii,i1)i1证.(1)可表本性：令M=(am-i,am-2,a2,ai):0aii,i=1,2,m-1,显然M=m!;N=0,1,2,m!-1,显然N=m!,其中m是大于n的任意整数。定义函数f:MNf(am-i,am-2,a2,ai)=am-i(m-1)!+am-2(m-1)!+a22!+ail!(*)显然，0=0(m-i)!+0(m-i)!+02!+0i!am-i(m-i)!+am-2(m-i)!+a22!+aii!(m-

7、i)(m-i)!+(m-2)(m-i)!+22!+ii!=m!-i(见Pi4)即0?f(am-i,am-2,a2,ai)m!-i由于f是用普通乘法和普通加法所定义的，故从而f无歧义。从而有一确定的数K(0Km!-i),使K=f(am-i,am-2,a2,ai)为证N中的任一数均可表示成上边(*)的形式，只要证明f是满射函数即可。但由于在两相等且有限的集合上定义的函数，满射性与单射性、双射性是等价的，故只须证明f是单射函数即可。否则,设存在某数K0N,有(am-i,am-2,a2,ai)(bm-i,bm-2,b2,bi)均属于M,使K0=f(am-i,am-2,a2,ai)且K0=f(bm-i,

8、bm-2,b2,bi)由于不相等，故必有某个j(m-i),使句切。不妨设这个j是第一个不使相等的，即ai=bi(imi,ji),ajbj且ajbj,从而由am-i(m-i)!+am-2(m-i)!+a22!+aii!=bm-i(m-i)!+bm-2(m-i)!+b22!+bii!就可有(bj-aj)j!+(bj-i-aj-i)(j-i)!+(b2-a2)2!+(b2-ai)i!=0但是(bj-aj)j!+(bj-i-aj-i)(j-i)!+(b2-a2)2!+(b2-ai)i!(bj-aj)j!-bj-i-aj-i(j-i)!+b2-a22!+b2-aii!j!-(j-i)(j-i)!+22!

9、+ii!=j!-(j!-i)=i矛盾，这说明f是单射函数。由于M=N=m!有限，故f是双射函数，当然是满射函数，从而0到m!-i中的任何一个数都可以表示成上边(*)的形式。故，由nN,都有(am-i,am-2,a2,ai)M,使得n=am-i(m-i)!+am-2(m-i)!+a22!+aii!这就证明了任何n可表示成以上形式。(2)唯一性：用证明单射的方法，就可以证明表示法的唯一性(表示方法见Pi4),留给读者。证明nC(ni,r)(ri)C(n,ri),并给予组合解释证.(参见P28(i-8-4)nC(n i,r)(n i)!r!(n r i)!n!(r i)!(n ri)!(r i) (

10、r i)C(n, r i)组合意义：(等式右边)由n个元素中取出r+i个元素组合(有C(n,r+i)种)，再从每个组合中取出i个(有r+i种)，全部结果为C(n,r+i)(r+i)。(等式左边)由此所得的全部结果相当于从n个元素中直接取i个元素(有n种)，但有重复，其重复数等于剩下的n-i个元素中取r个元素的组合C(n-i,r),故nC(n-i,r)=(r+i)C(n,r+i)。n试证等式：kC(n,k)n2ni证.证法一：根据二项式定理，(参见P29(1-8-5)(1+x)n=1+C(n,1)x+C(n,2)x2+xn两边对x求导，有n(1+x)n-1=C(n,1)+2C(n,2)x+nxn

11、-1n令x=1，即得kC(n,k)n2n1。k1证法二：组合意义：设有n个不同的小球，并有A、B两个合子，A合中恰好放入一个球，B合中可放入任意多个球。有两种放球方法：(1)(等式左边)先从n个球中选取k个，再从这k个球中任选一个放入A合，剩下的nk-1个球全部放入B合中，方案数共为kC(n,k)；k1(2)(等式右边)先从n个球中任选一个放入A合，剩下的n-1个球每个都有两种可能，要么放入B合，要么不放，方案数共为n2n-1；n1显然，两种放球方法等效，两种放球方案数相等，即kC(n,k)n2n1。k1有n个不同的整数，从中取出两组来，要求第1组的最小数大于另一个组的最大数.解设这n个不同的

12、数为m1m2m3mn。若假定第一组取k1个数，第二组取k2个数，并且令m=k1+k2(m2)，则要求第一组数里的最小数大于第二组的最大数，我们只要先从上边那n个数中任选m个数(有C(n,m)种选法)，再从这m个数中从大到小取k1个数作为第一组数(有k1=1,2,m-1共m-1种取法)，将其余k2个数作为第二组数，即可。故总方案数为nn1(m1)C(n,m)(n2)2n11(参见第3题等式)。m26个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案解第一次点火仅有一种选择，即点某个特定引擎的火；第二次点另一组某个引擎的火，有三种选择；第三次有2种,。即方案数为132

13、211=12。0 出现的次数相当于10-99， 100-999 ， 1000-9999, ,9999十位为零 个位为零18 81 81 180试求从1到1000000的整数中，0出现的次数解(参见P8)从1到1000000的整数中,以及1000000中的0的个数。10-99中的零的个数为：9100-999中的零的个数为：29十位、个位为零，故对百位的每一种取法，有两个零1000-9999 中的零的个数为：39有三位为零2 C32 9 9 C31 9 9 9有两位为零 有一位为零=27+486+2187=27004 93C439 9有四位零有三位零中的零的个数为:2C42999C419999有二

14、位零有一位零=36+972+8748+26244=36000中的零的个数为:594C；993C；9992C：9999c599999有五位零有四位零有三位零有二位零有一位零=45+1620+21870+131220+295245=4500001,000,000中的0的个数为：6故1到1,000,000的整数中0的个数为：9+180+2700+36000+450000+6=488895。n个完全一样的球放到r个有标志的盒(nr)中，无一空盒，试问有多少种方案解n和r都是正整数，而且rwn,试证下列等式:(a)PrnnPrT(b)Prn(nr1)Prn1nnn1(c)PrPr,rnnrn1nn(d)

15、PrPrrPr1n1nn1r、(e)Pr门r(Pr1Fr1LP.1)解(a)方法一Prn三匕n(n1)L(nr1)(nr)!n(n1)Ln1(r1)1n(n(n1)(r1)1!nPn11方法二(组合意义)等式左边：从n个元素种取r个元素做排列有Prn种，就是等式左边;等式右边：先从n个元素中拿出一个元素排在首位，有n种方法，然后再从剩下的n-1nnr-nnn1n1个兀素中取r-1个兀素做后面r-1位的排列，有Pr1种方法，按乘法原理，共有nR1种方(b)方法一Prnn!(n r)!n(n 1)L (n r 2)(n r 1)方法二(组合意义法)(n(nr 1) n(n 1)L n (r 1)

16、11)n!n (r 1)!(n r 1)Rn1等式左边：从n个元素中取r个元素做r位排列，有Prn种方案。等式右边：先从n个元素中取r-1个元素做r-1位排列，有Prn1种方法；再从剩下的n-r+1个元素中取1个元素，共有n-r+1种选法，按乘法原理，共有(nr1)Prn1方法一_nn!.一Prn(n1)L(nr2)(nr1)(nr)!n(n1)L(nr2)(nr2)(nr1)(nr)nrn(n1)L(nr1)(n1)r1nrn(n1)!nr(n1)r!-Prn1nr方法二：(组合意义法)等式左边：从n个元素中取r个元素做r位排列，其方案数为Prn；等式右边：从n个元素中先取出一个元素放在第一

17、位，有n种方法，再从剩下的n-1个元素种取出r个元素放在第2位，第r位，第r+1位，有Prn1种方法，这样就多了一位，故应除去第r+1位的选取方法，共有n-r种选法，故总方案为-P,n1。nr(d)方法一Prn1/I(n1)nL(nr2)(n1r)!(nr1)rnL(nr2)nL(nr2)(nr1)rnLn(r1)1n!rn!(nr)!(nr1)!PrnrPrn1方法二：(组合意义)等式左边：从n+1个不同的元素中取r个元素进行r位排列。其方案为Prn1；等式右边：(a)不取某特定元素b,则r个元素需从剩下的n个元素中取，然后做r位排列，共有P0种方案。(b)取定某特定元素b,则其余r-1个元

18、素需从剩下的n个元素中取，先做r-1位排列，共有Prn1种方法，再将特定元素b插入这r-1个元素形成的r个空隙中，有r种方法，故按乘法原理，共有rPrn种方案。(e)方法(根据(d)可得)Pn 1rPrnrPrn1Pn1rPn1rPnrr1r1n2n2n1nPrrPr1rPr1rPr1Pn2rPn2rPn1rPnrir1r1r1LLLPrr rPrr1 rPrr 11 LrPrn11 rPrn1rr1r!r(Pr1Pr1Ln 1 n 、Pr 1Pr 1)Pr 1Prr 1 r 1r!r(Prn1Prn；L方法二：组合意义(同样根据d)等式左边：从n+1个不同元素取r个元素做r位排列，其方案数为

19、：Prn1等式右边：设bi,b2,b3,bni是n-r+1个特定元素。(a)不取特定元素bi,b2,b3,hi-剩下的r个元素做全排列，有P：=r!种方案。(b)(1)：取特定元素bi，但不取特定元素b2,b3,bni，于是先在剩下的r个元素中取r-i个元素做排列，有Prr-I方法，然后将bi插入这r-i个元素的r个空隙，共有r种方法，故按乘法原理，有1种方案。(2)：取特定元素bi，但不取特定元素b3,bnir,于是先在剩下的r+1个元素中取r-1个元素做排列，有种方法，然后，将bi插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有rp；种方案。(n-r)：取特定元素”，但不取特定

20、元素bnir，于是先在剩下的n-1个元素中取r-1个元素做排列，有Prni1种方法，然后，将bi插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有rPj；种方案。(n-r+1)：取特定元素，先在剩下的n个元素中取r-1个元素做排列，有P*种方法，然后，将bi插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有rPji种方案。最后，按加法原理，共有：r!r(PrniPrni1L*8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案C?解先将5个球进行全排列，有5!种万法，再将三个空格插入5个球的6个空隙中，有3m1种方法，然后将这C；

21、5!2400n问有多少种方案解甲单位选4人，则乙单位只能选3人；另外男同志要5人，而乙单位的3人全是男同志，还差2名男同志，故甲单位的男同志人数应至少是2,至多为4。104151010415101041510768600223031214012一个盒子里有7个无区别的白球，5个无区别的黑球.每次从中随机取走一个球，已知前面取走6个，其中3个是白的.试问取第6个球是白球的概率.解已知前面取走6个球，有3个白球，则有3个黑球。6故总的取球方案是765543；35第六个球是白球的方案是76554325765543因此取出第6个球是白球的概率 P20.57 6 5 5 4 33求下图中从0至IJP的路

22、径数:(a)路分为两段：先从路径必须过A点；路径必须过道路AB;路径必须过A和C;。到A,32(a)(b)(c)再从A到P,则有:(b)路分为三段：先从2。到3A,25再从812A到B;再从45285603A至ijB;然后从B至ijP;57350(c)路分为三段：先从32O到A;再从6332A至ijC;然后从C到P;2(d)(采用排除法)从。到P的满足不过42402AB的路=从O到P的路一从。到P经过AB的路，因此:133501287350937另s=1,2,3,n+1,n2T(x,y,z)|x,y,zs,xz,n证而k13k33k23kk2k1试证:n1k2k1k33k5nk21nnn-(k

23、1)3k33kn3k1k1k113.3,-n11-nn1n321d31d(n1)-n1-nn13231131-n(n1)-(n1)n(n1)-(n1)233121(n1)-(n1)2n33n112(n1)(n2n13n1)23n112(n1)(nn)23n12(n1)n(n1)23211.24A=(a,b)|a,bCZ,0a9,0wbw5(a)求x-y平面上以A作顶点的长方形的数目.(b)求x-y平面上以A作顶点的正方形数目.解(a)先选定横作标，再选定纵坐标，其方案数为：106109656752222(b)求xy平面上以A作顶点的正方形数目。按边长分类：边长为1的正方形：9X5=45边长为2

24、的正方形：(9-1)X(5-1)=32边长为3的正方形：(9-2)X(5-2)=21边长为4的正方形：(9-3)X(5-3)=12边长为5的正方形：(9-4)X(5-1)=5故总的以xy平面上A点作顶点的正方形的数目，按加法原理可得数目为115.平面上有15个点Pi,P2,，P15,其中P1,P2,P3,P4,P5共线，此外不存在3点共线的.(a)求至少过15个点中两点的直线的数目.(b)求由15个点中3点组成的三角形的数目.解(a)(采用排除法)P5至少过15个点中两点的直线数目=在15个点中任选2个点将有一条直线从P1中选2点构成直线+P1P5所在的直线l15512296(b)(采用排除法

25、)由15个点中3点组成的三角形白数目=任在15个点中取3点构成三角形的数目一在个点RP5中取3点构成的“三角形”的数目15445S=1,2,，1000,a,bSS,使ab三0mod5,求数偶a,b的数目.解因为ab0mod5所以ab=5k(k是整数)1a1000,1b10001ab100000015k10000001k200000所以满足ab0mod5且1wa,bw1000的a,b的数目为2000006位男宾，5位女宾围一圆桌而坐(a)(b)(c)解(a)女宾不相邻有多少种方案所有女宾在一起有多少种方案一女宾A和两位男宾相邻又有多少种方案先将6位男宾作圆排列有Q65!120在将5位女宾插入6个

26、空格，每格一人，共有6X5X4X3X2X1=720按乘法原理：有120X720=86400、Q77(b)5位女宾在一起，可看作一人，与6位男宾一起，先做圆排列，有=6!=720然后5位女宾内部作线排列，有5!=120。所以，总方案为：720X120=86400Q(c)先将6个男宾做圆排列，共有Q6=120种方法。再将女宾A随便插入6个空格中的一个，有6种方法。然后将剩下的4个女宾插入5个空格中，但每个空格不限人数，故相当于将4个有区别一,一451=5X 6X 7X 8= 1680。的球放入5个不同的盒子中的放球方案(可重组合),共有4所以，按乘法原理，有120X6X1680=1209600种方

27、案。k和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数解先将kxn个来宾分成k堆，每堆n个人，有knn,n,(kn)!,n(k堆)n! n! n!(kn)! (n!)k再将每堆n个人做圆排列，有 故按乘法原理，有Qn = (n-1)!,共有(n 1)!种方法。(kn)!k (n (n!)从n个对象中取r个作圆排列，求其方案数目解每一个r个人围成的圈(圆排列)a1，a2,1)!k已知,ar 1(kn)!knK rn,k,将r个无区别的球放在n个有标志的盒子里，每盒至少k个球，试问有多少种方案解先将nk个球放入n个有标志的盒中，每盒k个球，其方案为1。再将剩下的r-nk个球放入这n个盒中，

28、每盒球数不限，其方案数为n(rnk)1rn(k1)1rnkn1故总的方案为rn(k1)1rn(k1)1nn1在r,s,t,u,v,w,x,y,z的排列中求y居x和z中间的排列数.解由于y必须居于x和z之间，故形成图象xyz,形成4个空格。其余r,s,t,u,v,w这6个元素，只能放在这4个空格处，这相当于将6个不同的小球放入4个不同的盒子中，允许空盒，6 6!4目盒内还要进行排列的方案数。故有:9!6!604803!6!方法2：将9个字母进行全排列，有9!中排列，而x,y,z这3个字母形成的3!个排列只看作一种排列xyz,故有：9!604803!解从一个顶点可引出7条线和第一条(从右到左)交的

29、有17,和第二条交的有 26条边十边形的任意三条对角线不共点.试求这凸十边形的对角线交于多少个点故和一个顶点引出的7条线相交的点为：17+26+35+44+53+62+71=84故和从10点引出的对角线交的点有个8410=840,但每个点重复了四次(因为每个点在两条线上，而每条线有两个端点)。故凸10边形(这样的)对角线交于-840210个点。4故也可为c4010987210C4321试证一整数是另一整数的平方的必要条件是除尽它的数的数目是整数证“必要性”。若整数n是另一个整数的平方，则 n一定可写成如下形式:nPi21P22Pe2其中 P1,P2,Pe 是 e (21+1)(22+1)(2e

30、+1)为奇数。(参见P7例4)个不同的素数。由于第9题可得，除尽 n的正整数数目为“充分性”。若除尽正整数n的正整数的数目为奇数。则 n一定是某个正整数的平方, 否则，n不是平方数，则n一定是可分解成如下形式：nPl R 2Pe e其中P1,P2,Pe是e个不同的素数，且1,2,e中至少有一个奇数是(21+1)(22+1)(2e+1)必为偶数，与充分性假设矛盾。(否则n为平方数)。于给出n rm 0n 1 r 1 n 2 r 2 Lm 11 m 22的组合意义证组合意义一：从(n+r+1)个元素1,2,n+r+1中取出(nr 1 m)个元素i1i2irir+2ir+2? ?in+r+1-m 的

31、个数是其中第r+1个位置上的元素岛可取r+1,r+2,r+1+m。当ir+1取(r+1+k)时(k=0,1,2,m),前边r个数i1,i2,ir可在1,2,r+1+(k-1)这(r+k)个数里取，故种取法；后边(n+r+1-m)-(r+1)=n-m个数 ir+2,in+r+1-m 可在r+1+k+1, ,n+r+1这(n+r+1)-(r+1+k)=n-k 个数中取，故有O根据乘法原理，当ir+1=r+1+k 时,这样的组合数为就有n rm 0nkrk。根据加法原理，对k=0,1,2,m作和,mkknmrmnr10mmo注：参见CombinatorialProblemsandExerciseby

32、0143.7L896cP18-42(i)P96P172st(i)Thenumberofthose(n+r+1-m)-tuplesof1,2,n+r+1Whose(r1)elementisr+k+1isrknk.Summingfork=0,1,2,m,wegetthekmkresult.组合意义二：(格路方法)等式左端：从点A(-r-1,0)到点C(-1,k)(k=0,1,2,m)直接经过点D(0,k)再到点B(n-m,m)的路径数(参见本题图1);等小右端：从点A(-r-1,0)到点B(n-m,m)的路径数。给出n 1 的组合意义r 1rr1r2nLrrrr证.组合意义一：等式右端是从n+r+

33、1个元素a1,a2,an1中取出r+1个作不允许重复的组合，结果不A.Aifl A_AllienA?七口 不 rih.A11 A A i Ad IAa花元Al A-.第16题图1,an 1中取出r个元素的组合，然后再加上 a3而成，其组合数为n 2-r即 A1A2A3。外乎有以下几种情况(参见P25等式3的组合意义)：(1)r+1个元素的组合中含有a1的，相当于从n个元素a2,a3,an1中取r个组合，其组合数为n(即A)。r(2)r+1个元素的组合中不含有a1，但又含有元素a2的。即一个(r-1)-组合。依a1来分，不外乎含a1和不含a1；不含a1的又依a2分，不外乎含a2和不含a2。不含a

34、1而含22的组合，相当于从n-1个元素a2,a3,an1中取r个元素的组合，然后加上a2而成，其组合数为n1t即A1A2。rr+1个元素的组合中不含a1和a2,但含有元素a3的。即不含a1，a2的依a3来分，不外乎含a3和不含a3。不含a1,a2而含a3的组合，相当于从n-2个元素a4,取出的r+1个组合元素中不含a1,a2,a3,anr1,但含有元素anr的。即不含a1，a2,a3,anr1的，又依anr来分，不外乎含有anr和不含有anr。不含Q,anr1而含anr的组合，相当于从n-(n-r-1)=r+1个元素anr,anr1,an1中取出r个元素的组合r1I-而加上anr而成，其组合数

35、为(即AA2Anr1Anr)orr1r由anr1,anr2,Hn1组成的(r+1)-组合的组合数为r1r(即AiaAnr)。而且A1(A1A2)(A1A2A3)(A1a2Anr1Anr)(A1A2Anr1Anr)(即全集)组合意义二：等式右端：从n+1个不同元素a1,a2,an,an+1,中任选r+1个元素的组合方案数；等式左端：从n+1个不同元素a1,a2,an,an+1,中选取r+1个元素，一定选元素ar+k+1(k=0,1,2,n-r),但是不选元素ar+k+2,an,an+1的组合方案数。证明n m 2n(nr)(r=0,1,2,n)mmmm1L0n1n1mmrmn证.借助P28等式4

36、,可知：rnrnr从而有mmm m 10 n1n 1m nn 0m nn 0m nn 1n1mnnnnnnm2n（用了P29等式5）n组合意义一：n个元素进行等式右端可看作从m个元素中取出n个元素进行组合。然后对这取出的染色（红，白）的所有方案，它为m2n;n等式左端可看作先从m个元素中取出k个元素（个数为m）,全部染以红色。再从剩kmk下的（m-k）个兀素中取出（n-k）个兀素（个数为），全部染以白色。根据乘法原理，从nkmmkm个元素中取出n个元素，k个染上红色，（n-k）个染上白色的方案数为，knkk=0,1,2,n;而从m个元素中取出n个元素染以红白两色的方案可分解成有0个，1个，n个

37、染以红色的总和。故根据加法原理，17题成立。组合意义二：等式右端：将从m个不同的小球中任意选出的n个小球放入两个不同的合子里，注意到每个小球都有两种放法，就得到了可能的放球方案数；等式左端：先从m个球中任选k个球放入第一个合子里（k=0,1,2,n）,再从剩下的m-k个球中任选n-k个球放入第二个合子里，然后对k从0到n求和，就得到了所有可能的放球方案效。从n个人中选r个围成一个圆圈，问有多少种不同的方案解.每一个r个人围成的圈（圆排列）a1,a2,a.1,a备溜2,ar1,ar（线排列）a2，a3,aar2，ar1即每一个r圈相当于r个r排列。故不同的方案数为若不计顺逆方向，则为 NiP(n

38、，r)-P(n,r) r1 n!r (n r)!1 n!2r (n r)!分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法.解.（略）（a）按照的要求，写出邻位对换法（排列的生成算法之二）的相应算法(b)写出按照邻位对换法由给定排列生成其下一个排列的算法解.(略)对于给定的正整数n,证明，当n1n1日人兴/r或，右n是旬数k22n,若n是偶数2时，C(n,k)的最大值.证取C(n,k)与C(n,k-1)进行比较。qn,k)/C(n,k-1)=(n-k+1)/k。当kn/2时，(n-k+1)/k1,即C(n,k)C(n,k-1);当kn/2时，(n-k+1)/k1

39、,即C(n,k)C(n,k-1);因此，得到当k=n/2或最接近n/2时，C(n,k)取得最大值。(a)用组合方法证明智和-(警都是整数.2n2n3n(n2)!士,(b)证明J*是整数.(n!)证(a)考虑2n个不同的球放入n个不同的合子里，每合两个的方案数。这个方案数应该是整数。对2n个球进行排列的方案数为(2n)!o而把2个球放入同一个合子里不计顺序，重复因2no因此，把2n个不2!是整数。2n同的球放入n个不同的合子里，每合两个的方案数是子是2。n个合子内部的排列共重复计算了2n次，故总的重复因子是同理，考虑3n个不同的球放入n个不同的合子里，每合3个的方案数。这个方案数应该是整数。对3

40、n个球进行排列的方案数为(3n)!o而把3个球放入同一个合子里不计顺序，重复因子是3!=23。n个合子内部的排列共重复计算了2n3n次，故总的重复因子是2n3n。因此，把3n个不同的球放入n个不同的合子里，每合3个的方案数是粤2。所以，-(曾是整数。2n3n2n3n(b)考虑n2个不同的球放入n个相同的合子里，每合n个的方案数。这个方案数应该是整数。子相同，放入不同的合子是没有区别的，其重复因子是n!。故此，总的重复因子是(n!)n+1。(n2)!(n!)n 1对n2个球进行排列的方案数为(n2)!。而把n个球放入同一个合子里不计顺序，重复因子是n!on个合子内部的排列共重复计算了(n!)n次

41、，故重复因子是(n!)n。另外，由于n个合因此，把n2个不同的球放入n个相同的合子里，每合n个的方案数是噜。所以,(n!)是整数。(a)在2n个球中，有n个相同.求从这2n个球中选取n个的方案数.(b)在3n+1个球中，有n个相同.求从这3n+1个球中选取n个的方案数.解(a)相当于从n个不同的小球中取出m个小球(0?mn),再从n个相同的小球中取出n-m个小乐，m=0,1,2,n的方案数。根据加法原理，这个方案数应该是：C(n,0)+C(n,1)+C(n,n)=2no同理，考虑3n个不同的球放入n个不同的合子里，每合3个的方案数。这个方案数应该是整数。(b)相当于从2n+1个不同的小球中取出

42、m个小球(0?mn),再从n个相同的小球中取出n-m个小球，m=0,1,2,n的方案数。根据加法原理，这个方案数应该是:C(2n+1,0)+ C(2n+1,1)+ C(2n+1,n)。证明在由字母表0,1,2生成的长度为3n(a) 0出现偶数次的字符串有n的字符串中1个；nn nn 2(b) 2n2n 2 L022n 3n 1q 2nq 7,其中 q2。证方法一：采用(串值)数学归纳法311基始当n=1时，0出现偶数次，长度为1的字符串有=2个(即1和2两个长度为1的字符串)。所证结论成立；归纳假设当n=m(1?mk)时，假设所证结论成立。即，0出现偶数次，长度为m的字3m1符串有31个；2归

43、纳当n=k+1时，0出现偶数次，长度为k+1的字符串包括两部分：(1)给0出现偶数次，长度为k的字符串后面再增加一位不是0的数(只能是1或2),k因此，按乘法原理，由归纳假设，此种字符串有3一12=3k+1个；2(2)给0出现奇数次，长度为由归纳假设，此种字符串有3kk的字符串后面再增加一位是3k 13k 1 人1 =个；220的数，因此，按乘法原理,所以，按加法原理，0出现偶戮3k 13k 1 1(3k+1)+3-1= 31 个。所22归纳完毕。方法二：采用指数型母函数方法设：an0出现偶数次，长度为nXA( x)an 一n 0 n!246(1 -2!4!6!X Xe e 2xe23x xe

44、 e2_21 3x (3x)一(一21!2!1(1 1) 321!、，3n 1所以，an -2一(规定 ao=1)，(b)利用组合意义法来证,长度为 k+1的字符串共有n的字符串的个数，则an的指数型母函数3233L ) (1?L )3!1!2!3!(32 1)x2(33 1)x3L2!3!23n 1考虑0出现偶数次，长度为n的字符串的个数。根据上面(a),已证其个数为种选择)放置上数 0,再另一方面，相当于先从n个位置中选取2m(02mn)个(有1或2 (有2n-2m种放法)，按乘法原理，是2n 2m个,2m 2n n 2n 2 n 2n q。因此，我们有02q3n 1)n q 3乙o22m

45、在剩下的n-2m个位置上放置数m=0,1,2,q(q2n)的方案数。2按加法原理，此方案数为n2nn2n2n02q5台教学机器m个学生使用.使用第1台和第2台的人数相等，有多少种分配方案解先从m个学生中选取k个使用第1台机器，再从剩下的m-k个学生中选取k个使用第2台机器，其余m-2k个学生可以任意使用剩下的3台机器，按乘法原理，其组合数为C(m,k)C(m-k,k)3(m-2k)。这里k=0,1,2,q(qm),于是，按加法原理，共有qC(m,k)C(mk,k)3(m2k/l使用方案。k0在由n个0及n个1构成的字符串中，在任意前k个字符中，0的个数不少于1的个数的字符串有多少(n,n+1)

46、(n+1,n+1)解转化为格路问题(弱领先条件一参见P36例4该例是强领先条件)。即从(0,0)至U(n,n),只能从对角线上方走，但可以碰到对角线。它可看作是从(0,1)到(n,n+1)的强领先条件(只能从对角线上方走，但不可以碰到对角线)的格路问题。更进一步的，它可看作是从(0,0)到(n,n+1)的强领先条件的格路问题(因为此种格路第一(0,1)口CQ丽0)C(2n,n 1) 奈48题图1步必到(0,1)格点)。故这样的字符串有n0(n1)1n1(n1)0nn1在1到n的自然数中选取不同且互不相邻的k个数，有多少种选取方案解设：g(n,k)为从1n中选取不同且互不相邻的k个数的方案数。于

47、是，按这k个数中有无数n而分为两种情况：(1)若选n,则必不能选n-1,故此种方案数为g(n-2,k-1);(2)若不选n,则可以选n-1,故此种方案数为g(n-1,k);所以，按加法原理，总的方案数g(n,k)=g(n-2,k-1)+g(n-1,k)。且只有当n2k-1时，g(n,k)0;否则g(n,k)=0。因此，可给定初始值：g(2k-1,k)=1,g(2k-2,k)=0。(a)在由5个0,4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个(b)在m个0,n个1组成的字符串中，出现01或10的总次数为k的字符串，有多少解(a)先将5个0排成一列：00000,一个1若插在两个0中间，就形成一个“010”，则同时出现“01”和“10”，计数为2;若插在两端，则仅出现一个01”或“10”，计数为1。现在要出现01”或“10”的总次数为4,可有两种办法：(1)先把两个1插入五个0所形成的四个空档内，再将剩下的两个1放在已才1入的1的前面，比如：0。按乘法原理，有 C(4,2)C(