《组合数学的参考问题详解卢开澄第四版修改版》由会员分享，可在线阅读，更多相关《组合数学的参考问题详解卢开澄第四版修改版（64页珍藏版）》请在金锄头文库上搜索。
1、word1.1 题从1，2，50中找两个数a，b，使其满足1|a-b|=5；2|a-b|5；解：1：由|a-b|=5a-b=5或者a-b=-5，由列举法得出，当a-b=5时，两数的序列为6，17，250，45，共有45对。当a-b=-5时，两数的序列为1，6，2，745，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，11，249，50，50，49这样的序列有49*2=98对。当此类推当|a-
2、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=5205个女生，7个男生进展排列，(a) 假如女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生A和B之间正好有3个女生的排列是多少？解：a可将5个女生看作一个单位，共八个单位进展全排列得到排列数为：8！5！，b用x表示男生，y表示空缺，先将男生放置好，共有8个空缺， Y X Y X Y X Y X Y X Y X Y X Y在其中任取5个得到女生两两不相邻的排
3、列数： C8，57！5！c先取两个男生和3个女生做排列，情况如下： 6. 假如A，B之间存在0个男生，A，B之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*2 1假如A，B之间存在1个男生，A，B之间共有4个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2假如A，B之间存在2个男生，A，B之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3假如A，B之间存在3个男生，A，B之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4假如A，B之间存在4个男生，A，B之间共有7个人，所有的排列应为
4、P4=C(5,4)*C(5,3)*7!*4!*2 5假如A，B之间存在5个男生，A，B之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2所以总的排列数为上述6种情况之和。1.3题 m个男生，n个女生，排成一行，其中m,n都是正整数，假如(a)男生不相邻; (b)n个女生形成一个整体； (c)男生A和女生B排在一起；分别讨论有多少种方案。解：(a) 可以考虑插空的方法。n个女生先排成一排，形成n+1个空。因为正好m个男生可以插在n+1个空中，形成不相邻的关系。如此男生不相邻的排列个数为(b) n个女生形成一个整体有n！种可能，把它看作一个整体和m个男生排在一起，如此
5、排列数有(m+1)!种可能。因此，共有种可能。(c)男生A和女生B排在一起，因为男生和女生可以交换位置，因此有2！种可能，A、B组合在一起和剩下的学生组成排列有(m+n-1)！(这里实际上是m+n-2个学生和AB的组合形成的)种可能。共有组合数为1.4题26个英文字母进展排列，求x和y之间有5个字母的排列数解：C24，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 题计算，11！+22！+33！+。+nn！解：由序数法公式可知
6、1!+1=2!22!+11!+1=3!33！+22！+11！+1=4！nn!+(n-1)(n-1)!+。+22!+11!+1= (n+1)!所以11！+22！+33！+。+nn！=(n+1)!1.7题试证：被2n除尽。证明：因因为(2n-1)!是整数所以能被2n除尽。18题求和的公因数数目。解：因为它们最大公因子为转化为求最大公因子能除尽的整数个数，能除尽它的整数是根据乘法法如此，能除尽它的数个数为 41*31=1271的正除数的数目是奇数。证明：设有, 如此一定有表达式，如此可知符合X围的和必成对出现，所以为偶数。又当a=b=n时，表达式=ab仍然成立。所以的正除数的数目是“偶数为奇数。1.
7、10题证任一正整数n可唯一地表成如下形式:,0aii,i1,2,。证：对n用归纳法。先证可表示性：当n=0,1时，命题成立。假设对小于n的非负整数，命题成立。对于n,设k!n(k+1)!,即0n-k!kk! 由假设对n-k!,命题成立，设，其中akk-1,，命题成立。再证表示的唯一性：设, 不妨设ajbj,令j=maxi|aibiajj!+aj-1(j-1)!+a11! =bjj!+bj-1(j-1)!+b11!, 矛盾，命题成立。1.11题证明nC(n-1,r)= (r+1)C(n,r+1),并给予组合解释.证：所以左边等于右边组合意义：等式左边：n个不同的球，先任取出1个，再从余下的n-1
8、个中取r个；等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。所以两种方案数一样。1.12题证明等式：证明：1.13题有N个不同的整数，从中间取出两组来，要求第1组的最小数大于另一组的最大数。解题思路：取法由大到小第1步：从N个数由大到小取一个数做为第一组，其它N-1个数为第二组，组合数为：cn,1*c(n-1,1)+c(n-1,2)-+c(n-1,n-1)第2步：从N个数由大到小取两个数做为第一组，其它N-2个数为第二组，组合数为：cn,2*c(n-2,1)+c(n-2,2)-+c(n-2,n-2)第n-2步：从N个数由大到小取n-2个数做为第一组，其它2个数为第二组，组合
9、数为：cn,n-2*c(2,1)第n-1步：从N个数由大到小取n-1个数做为第一组，其它1个数为第二组，组合数为：cn,n-1*c(1,1总的组合数为：1.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-100
10、000，共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份，要求是每份至少有一个球。如如下图所
11、示： 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种。而不同标志的球的排列有。所以共有8*5！种排列。8种排列如
12、下两类。因为要求空盒不相邻，途中1代表球a) 1 1 1 1b) 1 1 1 1在a)中剩下的一个球有四种位置，b)中剩下的一个球也有四种位置，两者合起来一共有8种和都是正整数，而且，试证如下等式：解：(a) 等式成立。(b) 等式成立。(c) 等式成立。(d) (e)利用(d)的结论可证明此题。1.19题n+m位由m个0，n个1组成的符号串，其中nm+1,试问不存在两个1相邻的符号串的数目。解：m个0进展排列，留出m+1个空挡，任选n 个空挡放1，共有C(m+1,n)种方案. 1.21题一个盒子里有7个无区别的白球，5个无区别的黑球，每次从中随机取走一个球，前面取走6个，其中3个是白的，试问
13、取第6个球是白球的概率。解：C6,2*C(5,2)*C(5,3)/C(5,3)C(7,3)C(6,3)=3/141.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
14、个男同志，乙单位出3个男同志，从甲单位出2个女同志. C(10,2)*C(15,3)*C(4,2)=1228501+2+3即为所求，总的方案数为768600PCAB1.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)，根据乘法法如此:(b)分两步走O(0,0)A(3,2),B(4,2)P(8,5)，根据乘法法如此:(c)分三步走: O(0,0)A(3,2),A(3,2)C(6,3), C(6,3)P(8,5), 根据乘法法如此: dAB封锁路径数加必经AB路径数即O(0,0)P(8,5)的所有路径数有加法法如此可得：s=1,2,n+1,n2,T=(x,y,z)|x,y,zs, xz, yz,试证
