组合数学参考答案(卢开澄第四版)60页.doc
《组合数学参考答案(卢开澄第四版)60页.doc》由会员分享，可在线阅读，更多相关《组合数学参考答案(卢开澄第四版)60页.doc（61页珍藏版）》请在冰点文库上搜索。
1.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，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=520
1.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!
*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个人，所有的排列应为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个男生排在一起，则排列数有（m+1）!
种可能。
因此，共有种可能。
（c）男生A和女生B排在一起，因为男生和女生可以交换位置，因此有2！
种可能，
A、B组合在一起和剩下的学生组成排列有（m+n-1）！
（这里实际上是m+n-2个学生和AB的组合形成的）种可能。
共有组合数为
1.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=1232
1.6题计算，1·1！
+2·2！
+3·3！
+。
。
。
+n·n！
解：
由序数法公式可知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题试证：
被2n除尽。
证明：
因
因为（2n-1）!
!
是整数所以能被2n除尽。
1．8题求和的公因数数目。
解：
因为
它们最大公因子为转化为求最大公因子能除尽的整数个数，能除尽它的整数是
根据乘法法则，能除尽它的数个数为41*31=1271
1.9题试证的正除数的数目是奇数。
证明：
设有,则一定有表达式，
则可知符合范围的和必成对出现，所以为偶数。
又当a=b=n时，表达式=ab仍然成立。
所以的正除数的数目是“偶数”为奇数。
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!
矛盾，命题成立。
1.11题证明nC（n-1,r）=（r+1）C（n,r+1）,并给予组合解释.
证：
所以左边等于右边
组合意义：
等式左边：
n个不同的球，先任取出1个，再从余下的n-1个中取r个；
等式右边：
n个不同球中任意取出r+1个，并指定其中任意一个为第一个。
所以两种方案数相同。
1.12题证明等式：
证明：
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.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种。
而不同标志的球的排列有。
所以共有8*5！
种排列。
8种排列如下两类。
因为要求空盒不相邻，途中1代表球
a）1111
b）1111
在a）中剩下的一个球有四种位置，b）中剩下的一个球也有四种位置，两者合起来一共有8种
1.17题和都是正整数，而且，试证下列等式：
解：
（a）等式成立。
（b）等式成立。
（c）等式成立。
（d）
（e）利用（d）的结论可证明本题。
1.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/14
1.20题甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志占5人，试问有多少中方案？
解：
1.甲单位出4个男同志，乙单位出1个男同志，从乙单位出2个女同志C（10,4）*C（15,1）*C（10,2）=141750
2..甲单位出3个男同志，乙单位出2个男同志，从甲单位出1个女同志,从乙单位出1个女同志。
C（10,3）*C（15,2）*C（4.1）*C（10,1）=504000
3..甲单位出2个男同志，乙单位出3个男同志，从甲单位出2个女同志.C（10,2）*C（15,3）*C（4,2）=122850
1+2+3即为所求，总的方案数为768600
P
C
A
B
1.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）,根据乘法法则:
（d）AB封锁路径数加必经AB路径数即O（0,0）→P（8,5）的所有路径数有加法法则可得：
1.23题令s={1,2,…,n+1},n≥2,T={（x,y,z）|x,y,z∈s,x证明：
要确定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取值共有种可能。
故。
（2）由x①x=y②x③y所以满足题意的x,y,z的组合数为++＝。
由于这两种方法是等价的，故可得。
证毕。
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=400000
1.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=96
2）有三种情况a：
没有P1P2P3P4P5这五个点的三角个数：
C103=120
b：
有这五个点的其中一个点：
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）=194000
C（5,1）*C（6,2）*C（5,2）*P（4,2）*7！
1.28题k和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数。
解：
若每个圆桌的的人数相等，则每个桌子有n个人。
因为圆周排列的个数为
因此本题的结果为。
1.29题从n个对象中取个r做圆排列，求其方案数目。
1<=r<=n
解：
c（n,r）*Q（r,r）=c（n,r）*（r-1）!
1.31题试证任意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！
除尽。
1．30题
（1）=n/r，1rn；
（2）=（n-r+1）/r,1rn；（3）=n/（n-r）,0rn；
解：
（1）：
n!
/（r!
（n-r）!
）n/r=n/r*（（n-1）!
/（（r-1）!
（n-r）!
））=n!
/（r!
（n-r）!
）=上式所以两式相等
（2）：
n!
/（r!
（n-r）!
）（n-r+1）/r=（n-r+1）/r*（（n!
）/（（r-1）!
（n-r+1）!
））=n!
/（r!
（n-r）!
）=上式所以两式相等
（3）：
n!
/（r!
（n-r）!
）n/（n-r）=（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都是正整数，，将r个无区别的球放在n个有标志的盒子里，每盒至少k个球，试问有多少种方案？
解：
首先从r个球中取出nk个球放入n个盒中，因为球是无区别的。
因此只有一种排列方案。
剩下的球，每个球放的时候都有n中可能。
因此方案数为.
1.34题在r,s,t,u,v,w,x,y,z的排列中求y居于x和z中间的排列数
解：
2*（5+4+3+2+1）*6！
=2430
1.35题凸十边形的任意三条对角线不共点。
试求这凸十边形的对角线相交于多少个点？
解：
根据题意，1个顶点有7条对角线，与它相邻的顶点有7条对角线，这样的点2个；
与它不相邻的顶点有6条对角线（有1条与它重复的），这样的点8个；
因此（2*C（7，1）*C（7，1）+8*C（6，1）*C（7，1））*（9+1）=4340
1.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题.给出+++…+=的组合意义。
解：
Y
B（m,n+r+1-m）
P’
P（k,r）
0kmX
如上图所示，表示（0，0）点到P点的路径数；
P点到P’点只有一步；=表示P’点到B点的路径数;表示（0，0）点到B点的路径数。
所以0点到B点的路径由0点到P点再从P点到P’点，最后从P’点到达B点。
*1*=+++…+=
1.41题分别写出按照字典序，有给定排列计算其对应序号的算法及有给定序号计算其对应排列的算法。
解：
利用“字典序法”生成下一排列的算法，计算该排列的对应序号，生成已知排列序号算法：
设intM为每一排列的对应序号初始时：
P1_P2_...Pi-1_Pi_Pi+1_...Pn_（其中P1_I.满足关系式Pj-1II.满足关系式Pi-1III.使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满足关系式Pi-1使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题给出的组合意义。
解：
设A={,,….,,……,},从A中取r+1个元素组合成C，考虑以下n-r+1种情况：
（1）∈C，则A需要从A\{}中取r个配合，构成C，共种可能
（2），则需要从中取r-1个，加上构成C，共中可能……
（n-r）则需从A\{}中取r个组合，再加上构成C，共种可能。
这时只有=1种可能。
故+++…++=
（法二）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
升级会员 