《组合数学习题答案卢开澄.pdf》由会员分享，可在线阅读，更多相关《组合数学习题答案卢开澄.pdf（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.11.1 题题从从11，2 2，5050中找两个数中找两个数aa，bb，使其满足，使其满足（1 1）|a-b|=5|a-b|=5；（2 2）|a-b|a-b|5 5；解：（1）：由|a-b|=5a-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|=
2、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.21.2 题题5 5 个女生，个女生，7 7 个男生进行排列，个男生进行排列，(a)(a)若女生在一起有多少种不同的排列？若女生在一起有多少种不同的排列？(b)(b)女生两两不相邻有多少
3、种不同的排女生两两不相邻有多少种不同的排列？列？(c)(c)两男生两男生 A A 和和 B B 之间正好有之间正好有 3 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 之间存
4、在 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!
5、*3!*2所以总的排列数为上述6 种情况之和。1.31.3 题题mm 个男生，个男生，n n 个女生，排成一行，其中个女生，排成一行，其中 m,nm,n 都是正整数，若都是正整数，若(a)(a)男生不相邻男生不相邻(m n1);(b)n(b)n 个女生形成一个整体；个女生形成一个整体；(c)(c)男生男生 A A 和女生和女生 B B 排在一起；排在一起；分别讨论有多少种方案。分别讨论有多少种方案。解：(a)可以考虑插空的方法。n 个女生先排成一排，形成n+1 个空。因为m n1正好 m 个男生可以插在 n+1 个空中，形成不相邻的关系。则男生不相邻的排列个数为p pnnn1m(b)n 个女生
6、形成一个整体有n！种可能，把它看作一个整体和m 个男生排在一起，则排列数有(m+1)!种可能。因此，共有n!(m1)!种可能。(c)男生 A 和女生 B 排在一起，因为男生和女生可以交换位置，因此有2！种可能，A、B 组合在一起和剩下的学生组成排列有(m+n-1)！(这里实际上是 m+n-2 个学生和 AB 的组合形成的)种可能。共有组合数为2!(m n1)!1.41.4 题题2626 个英文字母进行排列，求个英文字母进行排列，求 x x 和和 y y 之间有之间有 5 5 个字母的排列数个字母的排列数解：C（24，5）*13！1.51.5 题题求求 30003000 到到 80008000
7、之间的奇整数的数目，而且没有相同的数字。之间的奇整数的数目，而且没有相同的数字。解：根据题意，千位可以从 3，4，5，7，6 中选取，个位可以从 1，3，5，7，9 中选取；因此2*5*8*7+3*4*8*7=12321.61.6 题题计算，计算，1 11 1！+2+22 2！+3+33 3！+。+n+nn n！解：由序数法公式可知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.71.7 题题 试证：试证：(n 1)(n 2)(2n)被被 2 2n
8、 n除尽。除尽。n证明：因(2n)!2 n!(2n 1)!(n1)(n 2)(2n)n!(n1)(n 2)(2n)(2n)!(2n1)!nnn2n!2n!2因为(2n-1)!是整数所以(n 1)(n 2)(2n)能被 2n除尽。11 18 8 题题求求10和和20的公因数数目。的公因数数目。404040403010306030402030解：因为10 2*5 2*5*520 2*5 2*2*54030它们最大公因子为2*5转化为求 最大公因子 能除尽的整数个数，能除尽它的整数是ab2*5,0 a 40,0 b 30根据乘法法则，能除尽它的数个数为41*31=127121.91.9 题题试证试证
9、n的正除数的数目是奇数。的正除数的数目是奇数。22证明：设有0 a n,n b n,则一定有表达式n ab，则 可知符合范围的a和b必成对出现，所以为偶数。22又当 a=b=n 时，表达式n=ab 仍然成立。所以n的正除数的数目是“偶数1”为奇数。1.101.10 题题证任一正整数证任一正整数 n n 可唯一地表成如下形式可唯一地表成如下形式:证：对 n 用归纳法。先证可表示性：当 n=0,1 时，命题成立。假设对小于 n 的非负整数，命题成立。对于 n,设 k!n(k+1)!,即 0n-k!kk!,0a,0ai ii,ii,i1,2,1,2,。4030由假设对 n-k!,命题成立，设，其中
10、akk-1,，命题成立。再证表示的唯一性：设,不妨设 ajbj,令 j=maxi|aibiajj!+aj-1(j-1)!+a11!=bjj!+bj-1(j-1)!+b11!,(ajbj)j!(biai)i!j!ii!biaii!(biai)i!矛盾，命题成立。1.111.11题题证明证明 nC(n-1,r)=(r+1)C(n,r+1),nC(n-1,r)=(r+1)C(n,r+1),并给予组合解释并给予组合解释.证：nC(n 1,r)n(n 1)!(r 1)n!(r 1)n!(r 1)C(n,r 1)r!(n r 1)!(r 1)r!(n r 1)!(r 1)!(n r 1)!所以左边等于右边
11、组合意义：等式左边：n 个不同的球，先任取出 1 个，再从余下的 n-1 个中取 r 个；等式右边：n 个不同球中任意取出 r+1 个，并指定其中任意一个为第一个。所以两种方案数相同。1.121.12 题题证明等式：证明等式：kC(n,k)n2k1nn1n1nn1n1n1n1nnn C(n1,0)C(n1,1)C(n1,n1)n2右边证明：等式左边 nk1k1k1k1s0sn1.131.13 题题 有有 N N 个不同的整数，从中间取出两组来，要求第个不同的整数，从中间取出两组来，要求第 1 1 组的最小数大于另一组的最大数。组的最小数大于另一组的最大数。解题思路：（取法由大到小）第 1 步：
12、从 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总的组合数为：C(n,1)C(n1,1
13、)C(n1,2)C(n1,n1)C(n,2)C(n2,1)C(n2,2)C(n,n2)C(2,1)C(n,n1)C(1,1)2C(n2,n2)1.141.14 题题6 6 个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案？个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案？解：第 1 步从特定引擎对面的 3 个中取 1 个有 C(3,1)种取法，第 2 步从特定引擎一边的2 个中取 1 个有 C(2,1)种取法，第 3 步从特定引擎对面的2 个中取 1 个有 C(2,1)中取法，剩下的每边 1 个取法固定。所以共有 C(3,1)C(
14、2,1)C(2,1)=12种方案。1.151.15 题题求求 1 1 至至 10000001000000 中中 0 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；这样
15、总共的 0 数为：100000+99991+99901+99001+90001+1=488895。1.161.16 题题n n 个相同的球放到个相同的球放到 r r 个不同的盒子里，且每个盒子里不空的放法。个不同的盒子里，且每个盒子里不空的放法。解：如果用“O”表示球，用“|”表示分界线，就相当于用 r-1 个“|”把 n 个“O”分成 r 份，要求是每份至少有一个球。如下图所示：00|00000000|00000000|00000|000000对于第一个分界线，它有 n-1 种选择，对于第二个分界线只有 n-2 个选择，(因为分界线不能相临，如果相临它们之间就没有了球，这不合要求)，依次第
16、r-1 个分界线只有 n-(r-1)种选择。但是这样的分法中存在重复，重复度为(r-1)!,所以总得放法为：(n-1)*(n-2)*(n-r+1)/(r-1)!=C(n-1,r-1)。1.181.18 题题8 8 个盒子排成一列，个盒子排成一列，5 5 个有标志的球放到盒子中，个有标志的球放到盒子中，每盒最多放一个球，每盒最多放一个球，要求空盒不相邻，要求空盒不相邻，问有多少种排列方案？问有多少种排列方案？5解：要求空盒不相邻，这样球的位置共有8 种。而不同标志的球的排列有p5 5!。所以共有 8*5！种排列。8 种排列如下两类。因为要求空盒不相邻，途中1 代表球a)1111b)1111在 a
17、)中 剩下的一个球有四种位置，b)中剩下的一个球也有四种位置，两者合起来一共有8 种1.171.17 题题n和和r都是正整数，而且都是正整数，而且r n，试证下列等式：，试证下列等式：(a)p nprnn1r1nr(b)nr1pprnr(nr 1)p r!r(pnr1nr1(c)n1r1pnrnnrpn1r,r n(d)pn1rprp(e)n1pprr1)解：(a)npn1r1 nn(n1)!n!(nr)!(nr)!(nr 1)pnr等式成立。nn!n!pr1pr等式成立。(nr 1)!(nr)!n1nnn(n1)!n!(c)p等式成立。prnrrnr(nr 1)!(nr)!(b)(nr 1)
18、(d)pnrrpnr1n!n!n!(nr1)n!(n1)!n!rrn!(n1)!rr(nr)!(nr1)!(nr1)!(nr1)!(nr1)!(n1r)!pn1r(e)利用(d)的结论可证明本题。r!r(pnr1pn1r1prr1)pprprprpprprprr1r1rrprnrpn1rpr2r1rr1rrr1r1r1rpn1r1n1r1rpnr1n1rr1rr1r1r2r1rprpnr1p1.191.19 题题n+mn+m 位由位由 mm 个个 0 0，n n 个个 1 1 组成的符号串，其中组成的符号串，其中 nm+1,nm+1,试问不存在两个试问不存在两个 1 1 相邻的符号串的数目。相
19、邻的符号串的数目。解：m 个 0 进行排列，留出 m+1 个空挡，任选 n 个空挡放 1，共有 C(m+1,n)种方案.1.211.21 题题一个盒子里有一个盒子里有 7 7 个无区别的白球，个无区别的白球，5 5 个无区别的黑球，每次从中随机取走一个球，已知前面取走个无区别的黑球，每次从中随机取走一个球，已知前面取走6 6 个，其中个，其中3 3个是白的，试问取第个是白的，试问取第 6 6 个球是白球的概率。个球是白球的概率。解：C（6,2）*C(5,2)*C(5,3)/C(5,3)C(7,3)C(6,3)=3/1431.201.20 题题甲单位有甲单位有 1010 个男同志，个男同志，4
20、4 个女同志，乙单位有个女同志，乙单位有 1515 个男同志，个男同志，1010 个女同志，由他们产生一个个女同志，由他们产生一个 7 7 人的代表团，人的代表团，要求其中甲单位占要求其中甲单位占 4 4 人，而且人，而且 7 7 人中男同志占人中男同志占 5 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)
21、*C(10,1)=5040003.甲单位出 2 个男同志，乙单位出 3 个男同志，从甲单位出 2 个女同志.C(10,2)*C(15,3)*C(4,2)=1228501+2+3 即为所求，总的方案数为7686001.221.22 题题求图求图 1-221-22 中从中从 O O 到到 P P 的路经数的路经数:P(a)(a)路径必须经过路径必须经过 A A 点点;(b)(b)路径必须过道路路径必须过道路 AB;AB;(c)(c)路径必须过路径必须过 A A 和和 C C(d)(d)道路道路 ABAB 封锁封锁(但但 A,BA,B 两点开放两点开放)C解:(a)分两步走 O(0,0)A(3,2)
22、A(3,2)P(8,5)，根据乘法法则:AB3 235N 23 5603 243(b)分两步走 O(0,0)A(3,2),B(4,2)P(8,5)，根据乘法法则:N 3502332 31 22(c)分三步走:O(0,0)A(3,2),A(3,2)C(6,3),C(6,3)P(8,5),根据乘法法则:N 212240 （d）AB 封锁路径数加必经 AB 路径数即 O(0,0)P(8,5)的所有路径数有加法法则可得：583 243N 5231287350 9371.231.23 题题令令 s=1,2,n+1,n2,T=(x,y,z)|x,y,zs=1,2,n+1,n2,T=(x,y,z)|x,y,
23、zs,xz,yz,s,xz,yz,试证试证:|T|n1n12k 2k123n证明：要确定 x,y,z的取值，有两种方法，(1)可先确定 z,由题意可得 当 z=2 时，x 可取 1，y 可取 1，根据乘法法则，x,y 取值共有 11=12种可能；当 z=3 时，x 可取 1,2，y 可取 1,2，根据乘法法则，x,y 取值共有 22=22种可能；当 z=4 时，x 可取 1,2,3，y 可取 1,2,3,根据乘法法则，x,y 取值共有 33=32种可能；当 z=n+1 时，x 可取 1,2,n,y 可取 1,2,n,根据乘法法则，x,y 取值共有 nn=n2种可能。根据加法法则，当 z 取 2
24、,3,n+1 时，x,y 取值共有1 2 n 222kk1n2种可能。故|T|kk1n2。(2)由 xz,yz，可以分为三种情况：x=yz,x,y 可看作一个元素，这种情况等价于从1,2,n+1 中取 2 个进行组合，然后比较大小，小者为x(y),大者为 z,其组合数为n1；2n1xyz,等价于从 1,2,n+1 中取 3 个进行组合，然后比较大小可得x,y,z,其组合数为；3n1yxz,等价于从 1,2,n+1 中取 3 个进行组合，然后比较大小可得x,y,z,其组合数为。3n1n1n1。所以满足题意的 x,y,z的组合数为n1+n1+2332324nn1n1由于这两种方法是等价的，故可得|
25、T|k22。证毕。k1231.241.24 题题 A=(A=(a a,b)|,b)|a a,b,bZ,0Z,0a a9,09,0b b5 5(a)(a)求求 x-yx-y 平面上以平面上以 A A 作顶点的长方形的数目作顶点的长方形的数目.(b)(b)求求 x-yx-y 平面上以平面上以 A A 作顶点的正方形数目作顶点的正方形数目.解(a)：如图(a)，从图中可以看出，对于 x-y 平面上满足题意的任一顶点 A(a,b),除它本身以外，横坐标取值有 9 种可能，纵坐标取值有 5 种可能。顶点 A(a,b)与和它不在同一水平线或垂直线上的任一点(x,y)均可构成一个长方形。故满足要求的长方形的
26、数目为95=45 个。解(b)：如下图(b)，网格左边是 b 的取值，下面是 a 的取值。网格里是 x-y 平面上对应每个顶点 A(a,b)所得的正方形的数目。1.261.26 题题S=1,2,S=1,2,，10001000，a,ba,bS,S,使使 ab0 mod 5,ab0 mod 5,求数偶求数偶a,ba,b的数目的数目解：根据题意，ab 可以整除 5，2*C（200，1）*1000=4000001.251.25 题题平面上有平面上有 1515 个点个点 P P1 1,P,P2 2。1515，其中，其中 P P1 1P P2 2P P3 3P P4 4P P5 5共线，此外不存在共线，此
27、外不存在 3 3 点共线的。点共线的。(1)(1)求至少过求至少过 1515 个点中两点的直线的数目个点中两点的直线的数目(2)(2)求由求由 1515 个点中个点中 3 3 点组成的三角形的数目点组成的三角形的数目解：1)由题意知：P1P2P3P4P5共线，此外不存在3 点共线的，所以与这五点分别相连的其他的十点的直线数目为：5*10=50。另外十个点两两相连得直线数目为：C102=45又因为 P1P2P3P4P5共线，所以可算作一条至少2 点相连的直线所以至少过 15 个点中两点的直线的数目=50+45+1=962)有三种情况a：没有 P1P2P3P4P5这五个点的三角个数：C103=12
28、0b：有这五个点的其中一个点：5*C102 225c：有着五个点的两个点：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.271.27 题题6 6 位男宾，位男宾，5 5 位女宾围一圆桌而坐，位女宾围一圆桌而坐，（1 1）女宾不相邻有多少种方案？女宾不相邻有多少种方案？（2 2）所有女宾在一起有多少种方案？所有女宾在一起有多少种方案？（3 3）一女宾一女宾 A A 和两位男宾相邻又有多少种方案？和两位男宾相邻又有多少种方案？解：（1）若 5
29、 位女宾不相邻，先考虑 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.281.28 题题k k 和和 n n 都是正整数，都是正整数，knkn 位来宾围着位来宾围着 k k 张圆桌而坐，试求其方案数。张圆桌而坐，试求其方案数。解：若每个圆桌的的人数相等，则每个桌子有n 个人。因为圆周排列的个数为因此本题的结果为prnr(kn)!(kn)!k。nnnn
30、1.291.29 题题从从 n n 个对象中取个个对象中取个 r r 做圆排列，求其方案数目。做圆排列，求其方案数目。1=r=n1=r=n解：c(n,r)*Q（r,r）=c(n,r)*(r-1)!1.311.31 题题试证任意试证任意 r r 个相邻数的连乘：个相邻数的连乘：(n1)(n2)(nr)被被 r 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！除尽。51 13030 题题（1）=
31、n/rnrn 1nn，1rn；（2）=（n-r+1）/r,1rn；(3)r 1rr 1n 1n=n/(n-r)r,0rn；r n 1n解：（1）：r 1=n/r*(n-1)!/(r-1)!(n-r)!)=n!/(r!(n-r)!)=上式所以两式相等rn!/(r!(n-r)!)n/r（2）：n!/(r!(n-r)!)(n-r+1)/rnrn=（n-r+1）/r*(n!)/(r-1)!(n-r+1)!)=n!/(r!(n-r)!)=上式所以两式相等r 1n 1n（3）：r=（n-1）!/(r!(n-r-1)!)=n!/(r!(n-r)!)=上式所以两式相等rn!/(r!(n-r)!)n/（n-r）
32、1.321.32 题题在在 a,b,c,d,e,f,x,x,x,y,ya,b,c,d,e,f,x,x,x,y,y的排列中，要求的排列中，要求 y y 必须夹在两个必须夹在两个 x x 之间，问这样的排列数等于多少？之间，问这样的排列数等于多少？解：满足 y 必须加在两个 x 之间应为x y x y x然后再把 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.331.33 题题已知已知 r r
33、，n n，k k 都是正整数，都是正整数，r nk，将，将 r r 个无区别的球放在个无区别的球放在 n n 个有标志的盒子里，每盒至少个有标志的盒子里，每盒至少 k k 个球，试问有个球，试问有多少种方案？多少种方案？解：首先从 r 个球中取出 nk 个球放入 n 个盒中，因为球是无区别的。因此只有一种排列方案。剩下的球，每个球放的时候都有 n 中可能。因此方案数为n(r-nk).1.341.34 题题在在 r,s,t,u,v,w,x,y,zr,s,t,u,v,w,x,y,z的排列中求的排列中求 y y 居于居于 x x 和和 z z 中间的排列数中间的排列数解：2*（5+4+3+2+1）*
34、6！=24301.351.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.361.36 题题试证一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数试证一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数证明：设 N=P1a1
35、P2a2。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.371.37 题题.给出给出n r n1 r 1 n2 r 2nmr mn r 1 +=的组合意义。的组合意义。m0 m11 m220mm解：YB（m,n+r+1-m）PP(k,r)0kmXr k如上图所示
36、，表示（0，0）点到 P 点的路径数；kP 点到 P点只有一步；nmmknkn r 1表示（0，0）点到B 点的路径数。mk=mk表示 P点到 B 点的路径数;m所以 0 点到 B 点的路径由 0 点到 P 点再从 P 点到 P点，最后从 P点到达 B 点。0Mr knk Mk*1*mk=0n r n1 r 1 n2 r 2nmr mn r 1 +m0 m11 m220m=m 61.411.41 题题分别写出按照字典序，有给定排列计算其对应序号的算法及有给定序号计算其对应排列的算法。分别写出按照字典序，有给定排列计算其对应序号的算法及有给定序号计算其对应排列的算法。解：利用“字典序法”生成下一
37、排列的算法，计算该排列的对应序号，生成已知排列序号算法：设 intM 为每一排列的对应序号初始时：P1_P2_.Pi-1_Pi_Pi+1_.Pn_(其中 P1_P2_.Pi-1_Pi_Pi+1_Pn_)M=1（初始化）I.满足关系式 Pj-1Pj的 j 的 最大值，设为 i,即 i=max j|Pj-1Pj II.满足关系式 Pi-1Pk的 k 的 最大值，设为 j,即 j=max j|Pi-1PkIII.使 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_部分的顺序逆
38、转，得下一排列。V.V.判断(p_)排列是否与给定排列相同，相同则输出 M，ELSEM=M+1 GOTO （2）给定序列号计算排列算法：设 Int M 为每一排列的对应序号，M=N（N 为给定序号）设 IntK 为循环次数FOR（K=1；K+；K=N）满足关系式 Pj-1Pj的 j 的 最大值，设为 i,即 i=max j|Pj-1Pj 满足关系式 Pi-1Pk的 k 的 最大值，设为 j,即 j=max j|Pi-1=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)由
39、上知：左边=C(n,0)+C(n,1)+C(n,n)C(m,n)nn22nn1n由(x y)=C(n,0)x+C(n,1)xy+C(n,2)xy+C(n,n)yn令 x=y=1可得C(n,0)+C(n,1)+C(n,2)+C(n,n)=2左边=2nC(m,n)=右边命题得证。1.401.40 题题从从 n n 个人中选个人中选 r r 个围成一圆圈，问有多少种不同的方案？个围成一圆圈，问有多少种不同的方案？解：圆排列:共有 P(n,r)/r 种不同的方案。1.481.48 题题在由在由 n n 个个 0 0 及及 n n 个个 1 1 构成的字符串中，在任意前构成的字符串中，在任意前 k k
40、个字符中，个字符中，0 0 的个数不少于的个数不少于 1 1 的个数的字符串有多少？的个数的字符串有多少？解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1。7n n1n2r 1rn11.421.42 题题(a)(a)按照按照 1.411.41 的要求，写出邻位对换法（排列的生成算法之二）的相应算法的要求，写出邻位对换法（排列的生成算法之二）的相应算法.(b)(b)写出按照邻位对换法由给定排列生成其下一个排列的算法写出按照邻位对换法由给定排列生成其下一个排列的算法.解：1：给定排列求相应序号：设 IntI
41、 为每一排列的对应序号I=1（初始化）假定 A1：n和 E2：n；D2：n；B1：n都是整数数组，其中B1：n为给定序列 S1：A11i从2到n作始Aii，Dii，Ei 1终；S2：q 0；判断A1：n是否与B1：n相等若相等则输出I值否则I I1；S3：k从n降到2作始 Dk DkEk;p Dk;若 p k则作Ek-1;否则作始 若p 0 则作始 Ek1,q q1 终否则作始 p pq;r Ap;Ap Ap1;Ap1 r;转S2终终终2：给定序号求相应排列：设 IntI 为每一排列的对应序号I=1（初始化）M 为给定序列号假定 A1：n和 E2：n；D2：n；都是整数数组 S1：A11i从2
42、到n作始Ai i，Di i，Ei 1终；S2：q 0；判断 I 是否与 M 相等若相等则 i从1到n输出Ai；否则I I1；S3：k从n降到2作始 Dk Dk Ek;p Dk;若 p k则作Ek -1;否则作始若p 0 则作始 Ek 1,q q 1终否则作始 p p q;r Ap;Ap Ap 1;Ap 1 r;转S2终终终(a)由给定排列生成其下一个排列的算法从排列 p p1p2pn生成下一个排列S1：若在p p1p2pn中无一处于活动状态则停止。S2：求处于活动状态各数中的数值最大者，设为m，m和它箭头所指一侧相邻数互换位置。S3：比m大的数一律改变箭头的指向；转S1。8M=NN1或N1若N
43、是奇数221.431.43 题题对于给定的正整数对于给定的正整数 N N，证明，当，证明，当K 时，时，C(N,K)C(N,K)是最大值。是最大值。N若N是偶数2证明：要证明 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）/n1当 n 为奇数,k=(n-1)/2
44、 时（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）取最大值3n11.461.46 题题证明在由字母表证明在由字母表0,1,20,1,2生成的长度为生成的长度为 n n 的字符串中的字符串中.(a)0(a)0 出现偶数次的字符串有出现偶数次的字符串有个；个；2nnnn1nnq3n1(b)(b)2 2.2，其中，其中q 2n.2202q证：(a)归纳法：当 n=1 时,0 出现偶数次的字符串有(31+1)/2=2 个(即 1,2)
45、,成立。假设当 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 出现偶数次的字符串数，两边显然相等。()!(2n)!(3n)!1.441.44
46、题题（a）用组合方法证明n和nn都是整数。（b）证明nn1是整数。22 3(n!)(2n)!2nn!(2n1)!n!(2n1)!解：(a)方法一：因为：(2n)!2 n!(2n1)!所以n22nn2n!(2n1)!是整数，因此(2n)!是整数。n2方法二：设有 2n 个不同球放入 n 个不同的盒子里，每盒两个，这个方案数应该是整数。对 2n 个球进行排列得到方案数为(2n)!。而把 2 个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n 个盒子内部的排列共重复计算了2 次。得到 2n 个不同球放入 n 个不同的盒子里，每盒两个的方案数(2n)!n2若有 3n 个不同的球,放
47、入 n 个不同盒子,每个盒子放三个，这个方案应该是整数。对这 3n 个球进行排列得到方案数为(3n)!。而把 3 个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n 个盒子内部的排列共重复计算了3！次。得到 3n 个不同的球放入 n 个不同的盒子里，每盒三个的方案数2(3n)!(3n)!(3!)n3n2n(b)有n个不同的球，放入 n 个相同的盒子里，每盒 n 个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n2)!/(n!)n是整数。另外由于 n 个盒子相同，放入不同的盒子是没有区别的，应该把 n 个盒子的排列数n!除去。因此得到(n2)!/(n!)n+
48、1是整数。1.491.49 题题在在 1 1 到到 n n 的自然数中选取不同且互不相邻的的自然数中选取不同且互不相邻的 k 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)，且只有当 n2k-1 时,g(n,k)0,否则 g(n,k)=0,可给定初始值 g(2k-1,k)=1,g(2k-2,k)=0.91.451.45 题题(a)(a)在在 2n2n 个球中，有个球中，有 n n 个
49、相同个相同.求从这求从这 2n2n 个球中选取个球中选取 n n 个的方案数个的方案数.(b)(b)在在 3n+13n+1 个球中，有个球中，有 n n 个相同个相同.求从这求从这 3n+13n+1 个球中选取个球中选取 n n 个的方案数个的方案数.解(a）：有 n 个相同就有 n 个不相同取 n 个不相同和 0 个相同的为 C(n,n),取 n-1 个不相同的球和 1 个相同的球为 C(n,n-1)，等等。n所以总的方案数为Cn,0 Cn,1 Cn,n 2解(b）：方法同上，方案数为C2n1,0C2n1,1C2n1,n由于C(2n+1,0)=C(2n+1,2n+1),C(2n+1,n)=C
50、(2n+1,n+1)C 2n1,0 C 2n1,1 C 2n1,2n1 22n1则C2n1,0C2n1,1C2n1,n122n1 22n21.471.47 题题5 5 台教学机器台教学机器 mm 个学生使用，使用第一台和第二台的人数相等，有多少种分配方案？个学生使用，使用第一台和第二台的人数相等，有多少种分配方案？解：当使用第 1 台机器的学生为 n 个时，使用第 2 台机器的学生也为 n,从 m 个学生中选出 2n 个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3(m-2n)。所以总的方案数为C(m,2n)C(2n,n)3n0q(m2n)mq 21.