组合数学参考答案(卢开澄第四版)

11.1 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 从{1，2，……50}中找两个数{a，b}，使其满足（1）|a-b|=5；（2）|a-b|5；解：（1）：由|a-b|=5a-b=5或者a-b=-5，由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）……（50，45），共有45对。当a-b=-5时，两数的序列为（1，6），（2，7）……（45，50）也有45对。所以这样的序列有90对。（2）：由题意知，|a-b|5|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0；由上题知当|a-b|=5时有90对序列。当|a-b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）…（49，50），（50，49）这样的序列有49*2=98对。当此类推当|a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对，当|a-b|=0时有50对所以总的序列数=90+98+96+94+92+50=5201.2题5个女生，7个男生进行排列，(a)若女生在一起有多少种不同的排列？(b)女生两两不相邻有多少种不同的排列？(c)两男生A和B之间正好有3个女生的排列是多少？解：（a）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为：8！×5！，（b）用x表示男生，y表示空缺，先将男生放置好，共有8个空缺，YXYXYXYXYXYXYXY在其中任取5个得到女生两两不相邻的排列数：C（8，5）×7！×5！（c）先取两个男生和3个女生做排列，情况如下：6.若A，B之间存在0个男生，A，B之间共有3个人，所有的排列应为P6=C(5,3)*3!*8!*21．若A，B之间存在1个男生，A，B之间共有4个人，所有的排列应为P1=C(5,1)*C(5,3)*4!*7!*22．若A，B之间存在2个男生，A，B之间共有5个人，所有的排列应为P2=C(5,2)*C(5,3)*5!*6!*23．若A，B之间存在3个男生，A，B之间共有6个人，所有的排列应为P3=C(5,3)*C(5,3)*6!*5!*24．若A，B之间存在4个男生，A，B之间共有7个人，所有的排列应为P4=C(5,4)*C(5,3)*7!*4!*25．若A，B之间存在5个男生，A，B之间共有8个人，所有的排列应为P5=C(5,5)*C(5,3)*8!*3!*2所以总的排列数为上述6种情况之和。1.3题m个男生，n个女生，排成一行，其中m,n都是正整数，若(a)男生不相邻)1(nm;(b)n个女生形成一个整体；(c)男生A和女生B排在一起；分别讨论有多少种 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。解：(a)可以考虑插空的方法。n个女生先排成一排，形成n+1个空。因为1nm正好m个男生可以插在n+1个空中，形成不相邻的关系。则男生不相邻的排列个数为ppnmnn1(b)n个女生形成一个整体有n！种可能，把它看作一个整体和m个男生排在一起，则排列数有(m+1)!种可能。因此，共有)!1(!mn种可能。(c)男生A和女生B排在一起，因为男生和女生可以交换位置，因此有2！种可能，A、B组合在一起和剩下的学生组成排列有(m+n-1)！(这里实际上是m+n-2个学生和AB的组合形成的)种可能。共有组合数为)!1(!2nm1.4题26个英文字母进行排列，求x和y之间有5个字母的排列数解：C（24，5）*13！1.5题求3000到8000之间的奇整数的数目，而且没有相同的数字。解：根据题意，千位可以从3，4，5，7，6中选取，个位可以从1，3，5，7，9中选取；因此2*5*8*7+3*4*8*7=12321.6题计算，1·1！+2·2！+3·3！+。。。+n·n！解：由序数法 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 可知1!+1=2!2·2!+1·1!+1=3!3·3！+2·2！+1·1！+1=4！n·n!+(n-1)(n-1)!+。。。+2·2!+1·1!+1=(n+1)!所以1·1！+2·2！+3·3！+。。。+n·n！=(n+1)!－１1.7题试证：)2()2)(1(nnn被2n除尽。证明：因!)!12(!2)!2(nnnn!)!12(2!)!2(2!)2()2)(1(!2)2()2)(1(nnnnnnnnnnnnnn因为(2n-1)!!是整数所以)2()2)(1(nnn能被2n除尽。21．8题求4010和3020的公因数数目。解：因为1030404040405*5*25*2103020403060305*2*25*220它们最大公因子为30405*2转化为求最大公因子能除尽的整数个数，能除尽它的整数是300,400,5*2baba根据乘法法则，能除尽它的数个数为41*31=12711.9题试证2n的正除数的数目是奇数。证明：设有20,annbn,则一定有表达式2nab，则可知符合范围的a和b必成对出现，所以为偶数。又当a=b=n时，表达式2n=ab仍然成立。所以2n的正除数的数目是“偶数1”为奇数。1.10题证任一正整数n可唯一地表成如下形式:,0≤ai≤i,i＝1,2,…。证：对n用归纳法。先证可表示性：当n=0,1时，命题成立。假设对小于n的非负整数，命题成立。对于n,设k!≤n＜(k+1)!,即0≤n-k!＜k·k!由假设对n-k!,命题成立，设，其中ak≤k-1,，命题成立。再证表示的唯一性：设,不妨设aj＞bj,令j=max{i|ai≠bi}aj·j!+aj-1·(j-1)!+…+a1·1!=bj·j!+bj-1·(j-1)!+…+b1·1!,!)(!!!!)(!)(iabiabiijiabjbaiiiiiijj矛盾，命题成立。1.11题证明nC(n-1,r)=(r+1)C(n,r+1),并给予组合解释.证：(1)!(1)!(1)!(1,)(1)(,1)!(1)!(1)!(1)!(1)!(1)!nrnrnnCnrnrCnrrnrrrnrrnr所以左边等于右边组合意义：等式左边：n个不同的球，先任取出1个，再从余下的n-1个中取r个；等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。所以两种方案数相同。1.12题证明等式：112),(nnknknkC证明：11110111(1,0)(1,1)(1,1)211nnnnkksnnnnnnnCnCnCnnnkksL等式左边右边1.13题有N个不同的整数，从中间取出两组来，要求第1组的最小数大于另一组的最大数。解题思路：（取法由大到小）第1步：从N个数由大到小取一个数做为第一组，其它N-1个数为第二组，组合数为：c（n,1）*{c(n-1,1)+c(n-1,2)-…+c(n-1,n-1)}第2步：从N个数由大到小取两个数做为第一组，其它N-2个数为第二组，组合数为：c（n,2）*{c(n-2,1)+c(n-2,2)-…+c(n-2,n-2)}…第n-2步：从N个数由大到小取n-2个数做为第一组，其它2个数为第二组，组合数为：c（n,n-2）*{c(2,1)}第n-1步：从N个数由大到小取n-1个数做为第一组，其它1个数为第二组，组合数为：c（n,n-1）*{c(1,1}总的组合数为：(,1){(1,1)(1,2)(1,1)}(,2){(2,1)(2,2)(2,2)}(,2){(2,1)(,1)(1,1)}CnCnCnCnnCnCnCnCnnCnnCCnnC31.14题6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案？解：第1步从特定引擎对面的3个中取1个有C(3,1)种取法，第2步从特定引擎一边的2个中取1个有C(2,1)种取法，第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。所以共有C(3,1)•C(2,1)•C(2,1)=12种方案。1.15题求1至1000000中0出现的次数。解：当第一位为0时，后面6位组成的数可以从1-100000，共100000个0；当第二位为0时，当第一位取0-9时，后面5位可以取1-9999，此外当第一位取0时，后面5位还可以取为10000，这样共有9999*10+1=99991个0；同理第三位为0时，共有99901个0；第四位为0时，共有99001个0；第五位为0时，共有90001个0；第六位为0时，只有1个0；这样总共的0数为：100000+99991+99901+99001+90001+1=488895。1.16题n个相同的球放到r个不同的盒子里，且每个盒子里不空的放法。解：如果用“O”表示球，用“|”表示分界线，就相当于用r-1个“|”把n个“O”分成r份，要求是每份至少有一个球。如下图所示：00|00000000|00000000|00000|000000……对于第一个分界线，它有n-1种选择，对于第二个分界线只有n-2个选择，(因为分界线不能相临，如果相临它们之间就没有了球，这不合要求)，依次第r-1个分界线只有n-(r-1)种选择。但是这样的分法中存在重复，重复度为(r-1)!,所以总得放法为：(n-1)*(n-2)*…*(n-r+1)/(r-1)!=C(n-1,r-1)。1.18题8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？解：要求空盒不相邻，这样球的位置共有8种。而不同标志的球的排列有!555p。所以共有8*5！种排列。8种排列如下两类。因为要求空盒不相邻，途中1代表球a)1111b)1111在a)中剩下的一个球有四种位置，b)中剩下的一个球也有四种位置，两者合起来一共有8种1.17题n和r都是正整数，而且nr，试证下列等式：11111111111()()(1)(),()()!()nnnnnnrrrrrrnnnnnnrrrrrrrrnanbnrcrnnrdrerrpppppppppppppL解：(a)ppnrnrrnnrnnnn)!(!)!()!1(11等式成立。(b)ppnrnrrnnrnnrnrn)!(!)!1(!)1()1(1等式成立。(c)ppnrnrrnnrnnrnnrnn)!(!)!1()!1(1等式成立。(d)11!!!(1)!(1)!!!(1)!()!(1)!(1)!(1)!(1)!(1)!nnnrrrnnnnrnnnrrnnrrrnrnrnrnrnrnrppp(e)利用(d)的结论可证明本题。1111111112111111112111111!()nnrrnnrrrrrrrrrrrrnnrrrrrrrrrnnnrrrrrrrrrrrrrrrrrrrrpppppppppppppppppppLLLL1.19题n+m位由m个0，n个1组成的符号串，其中n≤m+1,试问不存在两个1相邻的符号串的数目。解：m个0进行排列，留出m+1个空挡，任选n个空挡放1，共有C(m+1,n)种方案.1.21题一个盒子里有7个无区别的白球，5个无区别的黑球，每次从中随机取走一个球，已知前面取走6个，其中3个是白的，试问取第6个球是白球的概率。解：C（6,2）*C(5,2)*C(5,3)/C(5,3)C(7,3)C(6,3)=3/1441.20题甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志占5人，试问有多少中方案？解：1.甲单位出4个男同志，乙单位出1个男同志，从乙单位出2个女同志C(10,4)*C(15,1)*C(10,2)=1417502..甲单位出3个男同志，乙单位出2个男同志，从甲单位出1个女同志,从乙单位出1个女同志。C(10,3)*C(15,2)*C(4.1)*C(10,1)=5040003..甲单位出2个男同志，乙单位出3个男同志，从甲单位出2个女同志.C(10,2)*C(15,3)*C(4,2)=1228501+2+3即为所求，总的方案数为7686001.22题求图1-22中从O到P的路经数:(a)路径必须经过A点;(b)路径必须过道路AB;(c)路径必须过A和C(d)道路AB封锁(但A,B两点开放)解:(a)分两步走O(0,0)→A(3,2)A(3,2)→P(8,5)，根据乘法法则:560353223N(b)分两步走O(0,0)→A(3,2),B(4,2)→P(8,5)，根据乘法法则:350334223N(c)分三步走:O(0,0)→A(3,2),A(3,2)→C(6,3),C(6,3)→P(8,5),根据乘法法则:240222113223N（d）AB封锁路径数加必经AB路径数即O(0,0)→P(8,5)的所有路径数有 加法 100以内进位加法和退位减法100以内进位加法题100以内进位加法100以内进位加法竖式整数加法运算定律推广到小数说课 法则可得：9373501287334223585N1.23题令s={1,2,…,n+1},n≥2,T={(x,y,z)|x,y,z∈s,x<z,y<z},试证:2111||223nknnTk证明：要确定x,y,z的取值，有两种方法，(1)可先确定z,由题意可得当z=2时，x可取1，y可取1，根据乘法法则，x,y取值共有1×1=12种可能；当z=3时，x可取1,2，y可取1,2，根据乘法法则，x,y取值共有2×2=22种可能；当z=4时，x可取1,2,3，y可取1,2,3,根据乘法法则，x,y取值共有3×3=32种可能；……当z=n+1时，x可取1,2,…,n,y可取1,2,…,n,根据乘法法则，x,y取值共有n×n=n2种可能。根据加法法则，当z取2,3,…,n+1时，x,y取值共有2222112nknk…种可能。故21||nkTk。(2)由x<z,y<z，可以分为三种情况：①x=y<z,x,y可看作一个元素，这种情况等价于从1,2,…,n+1中取2个进行组合，然后比较大小，小者为x(y),大者为z,其组合数为12n；②x<y<z,等价于从1,2,…,n+1中取3个进行组合，然后比较大小可得x,y,z,其组合数为13n；③y<x<z,等价于从1,2,…,n+1中取3个进行组合，然后比较大小可得x,y,z,其组合数为13n。所以满足题意的x,y,z的组合数为12n+13n+13n＝11223nn。PCAB5由于这两种方法是等价的，故可得2111||223nknnTk。证毕。1.24题A={(a,b)|a,b∈Z,0≤a≤9,0≤b≤5}(a)求x-y平面上以A作顶点的长方形的数目.(b)求x-y平面上以A作顶点的正方形数目.解(a)：如图(a)，从图中可以看出，对于x-y平面上满足题意的任一顶点A(a,b),除它本身以外，横坐标取值有9种可能，纵坐标取值有5种可能。顶点A(a,b)与和它不在同一水平线或垂直线上的任一点(x,y)均可构成一个长方形。故满足要求的长方形的数目为9×5=45个。解(b)：如下图(b)，网格左边是b的取值，下面是a的取值。网格里是x-y平面上对应每个顶点A(a,b)所得的正方形的数目。1.26题S={1,2,……，1000}，a,b∈S,使ab≡0mod5,求数偶{a,b}的数目解：根据题意，ab可以整除5，2*C（200，1）*1000=4000001.25题平面上有15个点P1,P2。。。Ｐ15，其中P1P2P3P4P5共线，此外不存在3点共线的。(1)求至少过15个点中两点的直线的数目(2)求由15个点中3点组成的三角形的数目解：1)由题意知：P1P2P3P4P5共线，此外不存在3点共线的，所以与这五点分别相连的其他的十点的直线数目为：5*10=50。另外十个点两两相连得直线数目为：C102=45又因为P1P2P3P4P5共线，所以可算作一条至少2点相连的直线所以至少过15个点中两点的直线的数目=50+45+1=962)有三种情况a：没有P1P2P3P4P5这五个点的三角个数：C103=120b：有这五个点的其中一个点：5*C102225c：有着五个点的两个点：10*C52=100由15个点中3点组成的三角形的数目=425故数目为C(15,2)-C(5,2)+1(b)C(5,0)C(10,3)+C(5,1)C(10,2)+C(5,2)C(10,1)1.27题6位男宾，5位女宾围一圆桌而坐，（1）女宾不相邻有多少种方案？（2）所有女宾在一起有多少种方案？（3）一女宾A和两位男宾相邻又有多少种方案？解：（1）若5位女宾不相邻，先考虑6位男宾围圆桌而做的方案数，然后女宾插入Q（6，6）*6*5*4*3*2=86400（2）把5位女宾看成一个整体，然后插入Q（6，6）*6*P(5,5)=86400（3）C（5，1）*C（6，2）*Q（8，8）=194000C(5,1)*C(6,2)*C(5,2)*P(4,2)*7！1.28题k和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数。解：若每个圆桌的的人数相等，则每个桌子有n个人。因为圆周排列的个数为rpnr因此本题的结果为knknnnnkn)!()!(。1.29题从n个对象中取个r做圆排列，求其方案数目。1<=r<=n解：c(n,r)*Q（r,r）=c(n,r)*(r-1)!1.31题试证任意r个相邻数的连乘：(1)(2)()nnnr被r！除尽.证明：由P（n,r）=n*(n-1)…（n-r+1）可知：（n+1）（n+2）…（n+r）=p（n+r,r）=c（n+r,r）*r!所以[（n+1）（n+2）…（n+r）]/r!=p（n+r,r）/r!=c（n+r,r）故任意个相邻数连乘可被r！除尽。61．30题（1）rn=n/r11rn，1rn；（2）rn=（n-r+1）/r1rn,1rn；(3)rn=n/(n-r)rn1,0rn；解：（1）：rnn!/(r!(n-r)!)n/r11rn=n/r*((n-1)!/((r-1)!(n-r)!))=n!/(r!(n-r)!)=上式所以两式相等（2）：rnn!/(r!(n-r)!)(n-r+1)/r1rn=（n-r+1）/r*((n!)/((r-1)!(n-r+1)!))=n!/(r!(n-r)!)=上式所以两式相等（3）：rnn!/(r!(n-r)!)n/（n-r）rn1=（n-1）!/(r!(n-r-1)!))=n!/(r!(n-r)!)=上式所以两式相等1.32题在a,b,c,d,e,f,x,x,x,y,y的排列中，要求y必须夹在两个x之间，问这样的排列数等于多少？解：满足y必须加在两个x之间应为xyxyx然后再把a，b，c，d，e，f插入，a插入时有6种选择，b插入时有7种选择，c插入时有8种选择，d插入时有9种选择，e插入时有10种选择，f插入时有11种选择，由此可得排列数N=11*10*9*8*7*6=11!/5!1.33题已知r，n，k都是正整数，nkr，将r个无区别的球放在n个有标志的盒子里，每盒至少k个球，试问有多少种方案？解：首先从r个球中取出nk个球放入n个盒中，因为球是无区别的。因此只有一种排列方案。剩下的球，每个球放的时候都有n中可能。因此方案数为nk)-(rn.1.34题在r,s,t,u,v,w,x,y,z的排列中求y居于x和z中间的排列数解：2*（5+4+3+2+1）*6！=24301.35题凸十边形的任意三条对角线不共点。试求这凸十边形的对角线相交于多少个点？解：根据题意，1个顶点有7条对角线，与它相邻的顶点有7条对角线，这样的点2个；与它不相邻的顶点有6条对角线（有1条与它重复的），这样的点8个；因此（2*C（7，1）*C（7，1）+8*C（6，1）*C（7，1））*（9+1）=43401.36题试证一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数证明：设N=P1a1P2a2。。。Pnan，P1，P2，。。。Pn是n个不同的素数，每个能整除尽数n的正整数都可以选取每个素数Pi从0到ai次，即每个素数都有ai+1种选择，所以能整除n的正整数的数目为(a1+1)(a2+1)。。。(ai+1)个。而设M=N2=P12a1P22a2。。。Pn2an，能被(2a1+1)(2a2+1)。。。2(ai+1)个整除。所以一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数。1.37题.给出0rmn+1111rmn+2222rmn+…+mmrmn0=mrn1的组合意义。解：YB（m,n+r+1-m）P’P(k,r)0kmX如上图所示，kkr表示（0，0）点到P点的路径数；P点到P’点只有一步；kmkmmn=kmkn表示P’点到B点的路径数;mrn1表示（0，0）点到B点的路径数。所以0点到B点的路径由0点到P点再从P点到P’点，最后从P’点到达B点。M0kkr*1*kmkn=M00rmn+1111rmn+2222rmn+…+mmrmn0=mrn171.41题分别写出按照字典序，有给定排列计算其对应序号的算法及有给定序号计算其对应排列的算法。解：利用“字典序法”生成下一排列的算法，计算该排列的对应序号，生成已知排列序号算法：设intM为每一排列的对应序号初始时：P1_P2_...Pi-1_Pi_Pi+1_...Pn_(其中P1_<P2_.<Pi-1_<Pi_<Pi+1_<Pn_)M=1（初始化）I.满足关系式Pj-1<Pj的j的最大值，设为i,即i=max{j|Pj-1<Pj}II.满足关系式Pi-1<Pk的k的最大值，设为j,即j=max{j|Pi-1<Pk}III.使Pi-1与Pj互换得(p_)=P1_P2_...Pi-1_Pi_Pi+1_...Pn_IV.(p_)=P1_P2_...Pi-1_Pi_Pi+1_...Pn_中的Pi_Pi+1_...Pn_部分的顺序逆转，得下一排列。V.判断(p_)排列是否与给定排列相同，相同则输出M，ELSEM=M+1GOTOΙ（2）给定序列号计算排列算法：设IntM为每一排列的对应序号，M=N（N为给定序号）设IntK为循环次数FOR（K=1；K++；K<=N）{满足关系式Pj-1<Pj的j的最大值，设为i,即i=max{j|Pj-1<Pj}满足关系式Pi-1<Pk的k的最大值，设为j,即j=max{j|Pi-1<Pk}使Pi-1与Pj互换得(p_)=P1_P2_...Pi-1_Pi_Pi+1_...Pn_(p_)=P1_P2_...Pi-1_Pi_Pi+1_...Pn_中的Pi_Pi+1_...Pn_部分的顺序逆转，得下一排列}输出(p_)排列。1.38题给出1121rnrnrrrrrr的组合意义。解：设A={1a,2a,….,1rna,……,1na},从A中取r+1个元素组合成C，考虑以下n-r+1种情况：(1)1a∈C，则A需要从A\{1a}中取r个配合，构成C，共rn种可能(2)ca1，,2ca则需要从},{\21aaA中取r-1个，加上2a构成C，共rn1中可能……(n-r)，，CaCaaarnrn121,...,,则需从A\{rnaaa,...,,21}中取r个组合，再加上rna构成C，共rr1种可能。,,...,,)1(21Caaarnrn这时只有rr=1种可能。故rn+rn1+rn2+…+rr1+rr=11rn（法二）C(n+1,r+1)是指从n+1个元素a1,a2,…,an+1中任取r+1个进行组合的方案数。左边：若一定要选an+1,则方案数为C(n,r).若不选an+1,一定要选an,则方案数为C(n-1,r).若不选an+1,an,…ar+2,则方案数为C(r,r).所有这些可能性相加就得到了总方案数。1.39题证明(m,0)C(m,n)+C(m,1)C(m-1,n-1)+…+C(m,n)C(m-n,0)=2nC(m,n)证明：由公式C(n,l)C(l,r)=C(n,r)C(n-r,l-r)其中：l>=r得：C(m,0)C(m,n)=C(m,n)C(n,0)同理：C(m,1)C(m-1,n-1)=C(m,n)C(n,1)…C(m,n)C(m-n,0)=C(m,n)C(n,n)由上知：左边=[C(n,0)+C(n,1)+…+C(n,n)]C(m,n)由()nxy=C(n,0)nx+C(n,1)1nxy+C(n,2)22nxy+…+C(n,n)ny令x=y=1可得C(n,0)+C(n,1)+C(n,2)+…+C(n,n)=2n左边=2nC(m,n)=右边命题得证。1.40题从n个人中选r个围成一圆圈，问有多少种不同的方案？解：圆排列:共有P(n,r)/r种不同的方案。1.48题在由n个0及n个1构成的字符串中，在任意前k个字符中，0的个数不少于1的个数的字符串有多少？解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1。81.42题(a)按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法.(b)写出按照邻位对换法由给定排列生成其下一个排列的算法.解：1：给定排列求相应序号：设IntI为每一排列的对应序号I=1（初始化）假定A[1：n]和E[2：n]；D[2：n]；B[1：n]都是整数数组，其中B[1：n]为给定序列123S[1]12[][][]1q0A[1n]B[1n]III1kn2AinAiiDiiEiSS：从到作始，，终；：；判断：是否与：相等若相等则输出值否则；：从降到作始D[k]D[k]E[k];pD[k];pkE[k]-1;p0E[k]1,qq1若则作否则作始若则作始终2ppq;rA[p];A[p]A[p1];A[p1]r;S否则作始转终终终2：给定序号求相应排列：设IntI为每一排列的对应序号I=1（初始化）M为给定序列号M=N假定A[1：n]和E[2：n]；D[2：n]；都是整数数组123S[1]12[][][]1q0Ii1nA[i]II1kAinAiiDiiEiSMS：从到作始，，终；：；判断是否与相等若相等则从到输出；否则；：从n2D[k]D[k]E[k];pD[k];pkE[k]-1;p0E[k]1,qq1降到作始若则作否则作始若则作始终2ppq;rA[p];A[p]A[p1];A[p1]r;S否则作始转终终终(a)由给定排列生成其下一个排列的算法。转指向；大的数一律改变箭头的比：数互换位置。和它箭头所指一侧相邻，设为的数值最大者，求处于活动状态各数中：停止。中无一处于活动状态则若在：生成下一个排列从排列13221121SmmmSppSppSppppnn91.43题对于给定的正整数N，证明，当11222NNNNKN或若是奇数若是偶数时，C(N,K)是最大值。证明：要证明C（N，K）是最大值，只需证明C（N，K）大于C（N，K-1）即可根据以往证明大小值的经验，可以用相减或是相除的方法来证明，就此题，相减不合适，采用相除可以消除等式中的一些项C（N，K）/C（N，K-1）=（N！/K！（N-K）！）*（（K-1）！（N-K+1）！/N！）=（N-K+1）/K当n为偶数，k=n/2时（N-K+1）/K=（（n+2）/n）*（2/n）=（n+2）/n>1当n为奇数,k=(n-1)/2时（N-K+1）/K=((n+3)/2)*(2/(n-1))=1+4/(n-1)>1当n为奇数,k=(n+1)/2时（N-K+1）/K=((n+1)2)*(2/(n+1))=1综上所述,当n取以上三种情况,C（N，K）取最大值1.46题证明在由字母表{0,1,2}生成的长度为n的字符串中.(a)0出现偶数次的字符串有312n个；(b)13122...2022nnnnqnnnq，其中22nq.证：(a)归纳法：当n=1时,0出现偶数次的字符串有(31+1)/2=2个(即1,2),成立。假设当n=k时,0出现偶数次的字符串有(3k+1)/2种。总的字符串有3种。0出现奇数次的字符串有(3k-1)/2种。当n=k+1时，0出现偶数次的字符串包括两部分：n=k时,0出现偶数次再增加一位不是0的，共有2(3k+1)/2种，0出现奇数次再增加一位0,共有(3k-1)/2种。所以共有2(3k+1)/2+(3k-1)/2=(3k+1+1)/2种，证毕。(b)等式左边第m项是0出现m次的字符串数，总和就是0出现偶数次的字符串数，右边由(a)得是0出现偶数次的字符串数，两边显然相等。1.44题（a）用组合方法证明nn2)!2(和nnn32)!3(都是整数。（b）证明)!(12)!(nnn是整数。解：(a)①方法一：因为：!)!12(!2)!2(nnnn所以!)!12(!2!)!12(!22)!2(nnnnnnnn!)!12(!nn是整数，因此nn2)!2(是整数。方法二：设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。对2n个球进行排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2次。得到2n个不同球放入n个不同的盒子里，每盒两个的方案数nn2)!2(②若有3n个不同的球,放入n个不同盒子,每个盒子放三个，这个方案应该是整数。对这3n个球进行排列得到方案数为(3n)!。而把3个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了3！次。得到3n个不同的球放入n个不同的盒子里，每盒三个的方案数nnnnn23)!3()!3()!3((b)有2n个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n2)!/(n!)n是整数。另外由于n个盒子相同，放入不同的盒子是没有区别的，应该把n个盒子的排列数n!除去。因此得到(n2)!/(n!)n+1是整数。1.49题在1到n的自然数中选取不同且互不相邻的k个数,有多少种选取方案？解:设从1-n中选取互不相邻的k个数的方案为g(n,k)。若选n，则方案为g(n-2,k-1),若不选n,则方案数位g(n-1,k).显然g(n,k)=g(n-2,k-1)+g(n-1,k)，且只有当n≥2k-1时,g(n,k)>0,否则g(n,k)=0,可给定初始值g(2k-1,k)=1,g(2k-2,k)=0.101.45题(a)在2n个球中，有n个相同.求从这2n个球中选取n个的方案数.(b)在3n+1个球中，有n个相同.求从这3n+1个球中选取n个的方案数.解(a）：有n个相同就有n个不相同取n个不相同和0个相同的为C(n,n),取n-1个不相同的球和1个相同的球为C(n,n-1)，等等。所以总的方案数为nnnCnCnC2,1,0,解(b）：方法同上，方案数为nnCnCnC,121,120,12由于C(2n+1,0)=C(2n+1,2n+1),…,C(2n+1,n)=C(2n+1,n+1)12212,121,120,12nnnCnCnC则2121221,021,121,22nnCnCnCnn1.47题5台教学机器m个学生使用，使用第一台和第二台的人数相等，有多少种分配方案？解：当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3(m-2n)。所以总的方案数为23),2()2,(0)2(mqnnCnmCqnnm1.50题(1)在有5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个？(2)在有m个0，n个1组成的字符串中，出现01或10的总次数为k的字符串，有多少个？解：(1)、先将5个00000排成一排，1若插在两个0中间，即：“010”则出现2个“01”或“10”；若插在两端，则出现1个“01”或“10”；要使出现“01”，“10”总次数为4，有两种办法：1、把两个1插入0的空当内，剩下的1插入1的后面（类似010111000）。2、把1个1插入0的空当，再取两个1分别插入两端，剩下的1插入1的前面。（类似10100011）。由1和2得：30*3*31424CC(2)、m个0产生m-1个空当。若k为偶数时：要得到出现“01”与“10”总次数为k，可以先按上题中1的情况讨论，则在m-1个空当中分别插入2k个1即可，也就是21kmC。剩下的1如何插入的问题与书P20页的 定理 三点共线定理勾股定理的证明证明勾股定理共线定理面面垂直的性质定理 1.2类似(在n个不同元素中取r个允许重复的组合，其组合数为（C（n+r-1,r)），在这里无区别的球的个数也就是剩下的1的个数（即n-2k），盒子的个数也就是插入到m-1个空当中的1的个数(即2k)，则得出剩下的1的插入方法有21knnC。即第一种情况的总的插入方法为：2121*knnkmCC。同理可得，按2的情况讨论后的第二种情况的总的插入方法为：2221221*knnkmCC。1和2得总的插入方法为：22212212121**knnkmknnkmCCCC。若k为奇数时：则必有且只有一个1插入字符串的头或尾,剩下的1按照1的方法插入,只有这样才能使k为奇数。所以插入的总方法为：211211**2knnkmCC。1.51题从N={1,2,…,20}中选出3个数，使得没有两个数相邻，问有多少种方案？解：相当于从N={1,2,…,20}个数中取3个作不相邻的组合，故方案数为C(20-3+1,3)=C(18,3)种1.52题从s={1,2,n}中连取k个数，使之没有两个数相邻，求不同方案数。解：在n个数中选k个数，使之没有两个数相邻，相当于在n-k+1位置中插入k个数，k个数中没有俩个数相邻。有!)!1(1kknCkkn种方案。有定理1.4直接可得。1.53题把n个无区别的球放进有标志1，2，…，n的n个盒子中，每个盒子可放多于一个球，求有多少种方案？解：把n个无标志的球放进n个有标志的盒子中，每个盒子允许多于一个球是允许重复的组合所以是nnn1=nn12111.54题.m个1，n个0进行排列，求1不相邻的排列数.设n>m.解：相当于n个0排列后,使m个1做不相邻的插入，共产生n+1个位置.第一个1插入有n+1种情况，第二个是n种情况…第m个1插入就有n-m+1种情况。所以是（n+1）（n）（n-1）…（n-m+1），即此题解为pn+1m。1.55题偶数位的对称数，即从左向右读法与从优向左的读法相同，如3223。试证这样的数可被11整除。证明：根据所有偶数位置上的数字及所有奇数位置上的数字分别相加，再求出两个和的差，如果所得的差能被11整除，那么这个整数必能被11整除。例如12344321，偶数位上是：2，4，3，1。奇数位上是：1，3，4，2因为对称数是偶数个，所以偶数为相加与奇数为相加的和是相等的，他们的差是零，而零能能被任何数整除，所以原题成立。证毕。1.56题n个男人与n个女人沿一圆桌坐下，问两个女人之间坐1个男人的方案数。又m个女人n个男人，且m<n，沿一圆桌坐下，求无两个女人并坐的方案数。解：根据题意，两个女人之间坐1个男人的方案数Q(n,n)*P(n,n)无两个女人并坐的方案数Q(n,n)*P(n,m)1.57题n个人分别沿着两张圆坐下，一张r人，另一张个n-r人，试问有多少种不同的方案数？解：C（n,r）*(r-1)!(n-r-1)!1.58题一圆周上n个点标以n,,2,1。每一点与其它n-1个点连以直线，试问这些直线交于圆内有多少点？解：这些直线交于圆内有C（n,4）个点每4个点形成矩形，其对角线有一个交点，故圆内交点有：)3)(2)(1(2411234)3)(2)(1()4,(nnnnnnnnnC因为四个点连在一起构成一个四边形，这个四边形的对角线相交于一个点，求这些直线交于圆内多少点就是求这些点能构成几个四边形，即转化为从n个点取出四个进行组合2.1题求序列{0，1，8，27，3n}的母函数。解：由序列可得到32333()23nGxxxxnx因为23111nxxxxx2311()'12341nxxxnxx设2311()()'23(1)1nnpxxxxxnxnxx2222221[()]'123(1)nnpxxxxnxnx设2223212()[()]'23(1)nnqxxpxxxxnxnx3323231[()]'123(1)nnqxxxnxnx3233313[()]'23(1)nnxqxxxxnxnx由以上推理可知[()]'xqx=,[7*94*(6)],nn所以可通过求得[()]'xqx得到序列的母函数：32()4Gxxxx2321()()[34(3)]6nHxFxdxxxnx122.2题已知序列343,,,,333n，求母函数解：3*2*14*3*2(3)*(2)*(1)()3*2*13*2*13*2*1nnnnGxx=1[3.2.14.3.2(3)(2)(1)]6nxnnnx211()()[3.24.3(3)(2)]6nFxGxdxxxnnx2321()()[34(3)]6nHxFxdxxxnx3431()()[]6nIxHxdxxXx因为23111nxxxx所以211()(1)61Ixxxx所以31()[]'''61xGxx就是所求序列母函数2.3题已知母函数2378()1354xGxxx，求序列{na}。解：2378()1354xGxxx=xxxBxA6149176191由23111nxxxx得277(19(9)(9))19nxxxx244(1(6)(6)(6))16nxxxx所以由两式相加得：对应序列{na}={11，39，,[7*94*(6)],nn}2.4题已知母函数239()156xGxxx，求序列{na}。解：239()156xGxxx=1218171817ABxxxx则na=82*(1)*7nn2.5题设2nnGF，其中nF是Fibonacci数。证明：1230nnnGGG，n=2.3.4…..求{012,,,GGG}的母函数。解：(1).已知2nnGF则123nnnGGG=222243nnnFFF22122nnnFFF212223nnnFFF222324nnnFFF则222243nnnFFF则1230nnnGGG(2)．01122()()nnnnGxGGxGGx=122011222nnnnnnGGxxGxxGx=22010202()nnnnnnGGxxGxGxGx=2010()()GGxxGxxGxGx=21()()xGxxGxx21()1xGxxx132.6题求序列{1，0，2，0，3，0，}的母函数。解：序列na=20(1)nnnx=2200nnnnnxx=220011(21)22nnnnnxx=22111()'2121xxx=221(1)x2.7题设nxnxxxG2642)1(4321=1/(1-x^2)^2求GxGx222)1(,)1(解：设246211234(1)111nxTGxxxnxxxLL22)1(1)1(11xxxxxxG所以1）nxxxxxxGx24222222111)1()1()1(2）1)1(1)1()1(222222xxGx2.8题求下列序列的母函数：(1)1,0,1,0,1,0，…(2)0,-1,0,-1,0,-1,…(3)1,-1,1,-1,1,-1,…解：(1)nxxxG2421211x(2)1253nxxxxG242221(1)11nxxxxxxxxLL(3)nnxxxxx)1(14322242422111(1)(1)111xxxxxxxxxxxLL2.9题设nxnxxxG221063132证明：(1)nxnxxxGx)1(4321)1(32(2)nxxxGx221)1((3)因为1)1(3Gx，所以有3)1(1xG证明（1）2232211136(1)123(1)2(1)(1)nnnGxxxxGxxnxxx（2）展开(1-x2)G=(1+x)/(1-2x+x2)当1x时有1111xxx(3)3232(1)(133)(136)xGxxxxx=23423451361015391830xxxxxxxx234391830xxxx34563610xxxx=131(1)Gx2.10题nxnxxxH3320104132证明(1)022)1(nnxnGHx(2)求H的表达式。证明(1)设H的第K+1项为hk，则hk=33n=1*2*3)1)(2)(3(kkk=6611623kkk，设G的前K+1项的和为Gk，则Gk=kkkg0=22+23+…+22k14而22+23+…+22k=1+22*3+23*4+…+2)1(*)2(kk=1+21[3*2+4*3+…+(k+2)(k+1)]=1+21(1+22+32+…+k2+3+6+…+3k+2+2+…+2)①{注释：均为k项，分别为平方数列，等差数列，常数列}=1+21[61k(k+1)(2k+1)+2)1(3kk+2k]=1+12)1)(2(2kkk+4)1(3kk+k=121212)1(9)1)(2(2kkkkkk=6611623kkk=hkH=xG1(2)由H=1+4x+10x2+20x3+…+(33n)xn+…=1+x1*2*32*3*4+1*2*33*4*5x2+…+nxnnn1*2*3)1)(2)(3(+…对其3次积分得H=)1(63xx，对此积分式3次求导得H=((()1(63xx)))’’&r