组合数学参考答案(卢开澄第四版)60页 下载本文

组合数学 双卢 答案

1.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=520

1.2题 5个女生,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个得到女生两两不相邻的排列数: 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)男生不相邻(m?n?1); (b)n个女生形成一个整体; (c)男生A和女生B排在一起; 分别讨论有多少种方案。

解:(a) 可以考虑插空的方法。

n个女生先排成一排,形成n+1个空。因为m?n?1正好m个男生可以插在n+1个空中,形成不相邻的关系。

则男生不相邻的排列个数为

ppnn?n?1m

(b) n个女生形成一个整体有n!种可能,把它看作一个整体和m个男生排在一起,则排列数有(m+1)!种可能。 因此,共有n!?(m?1)!种可能。

(c)男生A和女生B排在一起,因为男生和女生可以交换位置,因此有2!种可能, A、B组合在一起和剩下的学生组成排列有(m+n-1)!

(这里实际上是m+n-2个学生和AB的组合形成的)种可能。共有组合数为2!?(m?n?1)! 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

1.7题 试证:(n?1)(n?2)?(2n)被2n除尽。

n证明:因(2n)!?2n!(2n?1)!!

(n?1)(n?2)?(2n)n!(n?1)(n?2)?(2n)(2n)!???(2n?1)!! nnn2n!2n!2

1

因为(2n-1)!!是整数所以(n?1)(n?2)?(2n)能被2n除尽。

1.8题 求10和20的公因数数目。

404040403010306030402030解:因为10?2*5?2*5*5 20?2*5?2*2*5

4030 它们最大公因子为2*5转化为求 最大公因子 能除尽的整数个数,能除尽它的整数是

ab 2*5,0??a??40,0??b??30

根据乘法法则,能除尽它的数个数为 41*31=1271

21.9题 试证n的正除数的数目是奇数。

22证明:设有0?a?n,n?b?n, 则一定有表达式n?a?b,

则 可知符合范围的a和b必成对出现,所以为偶数。

22又当a=b=n时,表达式n=a?b仍然成立。 所以n的正除数的数目是“偶数?1”为奇数。 1.10题 证任一正整数n可唯一地表成如下形式:

证:对n用归纳法。

先证可表示性:当n=0,1时,命题成立。 假设对小于n的非负整数,命题成立。 对于n,设k!≤n<(k+1)!,即0≤n-k!<k·k!

,0≤ai≤i,i=1,2,…。

4030由假设对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!,

(aj?bj)?j!??(bi?ai)?i!?j!??i?i!??bi?ai?i!??(bi?ai)?i! 矛盾,命题成立。

1.11题 证明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)!所以左边等于右边

组合意义:等式左边:n个不同的球,先任取出1个,再从余下的n-1个中取r个;

等式右边:n个不同球中任意取出r+1个,并指定其中任意一个为第一个。 所以两种方案数相同。 1.12题 证明等式:

?kC(n,k)?n2k?1nn?1

?n?1?n?n?1?n?1?n?1?n?1?n?n?nC(n?1,0)?C(n?1,1)?L?C(n?1,n?1)?n2?右边 ?? 证明: 等式左边??n????????k?1?k?1?k?1?k?1?s?0?s?n1.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} 总的组合数为:

2

C(n,1)?{C(n?1,1)?C(n?1,2)??C(n?1,n?1)}?C(n,2)?{C(n?2,1)?C(n?2,2)???C(n,n?2)?{C(2,1)?C(n,n?1)?C(1,1)}?C(n?2,n?2)}

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个有标志的球放到盒子中,每盒最多放一个球,要求空盒不相邻,问有多少种排列方案?

5解:要求空盒不相邻,这样球的位置共有8种。而不同标志的球的排列有p5?5!。所以共有8*5!种排列。 8种排列如下两类。因为要求空盒不相邻,途中1代表球

a) 1 1 1 1

b) 1 1 1 1

在a)中 剩下的一个球有四种位置,b)中剩下的一个球也有四种位置,两者合起来一共有8种 1.17题 n和r都是正整数,而且r?n,试证下列等式: (a)p?nprnn?1r?1nr(b)nr?1pprnr?(n?r?1)p?r!?r(pnr?1nr?1(c)n?1r?1pnr?nn?rpn?1r,r?n

(d)pn?1r?p?rp(e)n?1?p?L?prr?1) 解:(a) n(n?1)!n!pr?1?n?(n?r)!?(n?r)!?n?1npnr等式成立。

nn!n!??pr?1pr等式成立。

(n?r?1)!(n?r)!n?1nnn(n?1)!n!(c) ????pn?r(n?r?1)!(n?r)!pr等式成立。

n?rr(b) (n?r?1)?(n?r?1)?(d)

n!n!n!(n?r?1)n!(n?1)!?n!?r?r?n!(n?1)!pr?rpr?1?(n?r)!?r?(n?r?1)!?(n?r?1)!?r?(n?r?1)!?(n?r?1)!?(n?1?r)!?nnpn?1r

(e)利用(d)的结论可证明本题。

r!?r(pnr?1?pn?1r?1?L?prr?1)?p?p?rp?rp?rp?p?rp?rp?Lrr?1r?1rrrr?1r?1r?1r?1rr?1r?1r?2r?1r?rpn?rpn?1?L?rpr?2r?1rr?1n?1r?1?L?rpn?1r?1?rp?nr?1n?1r

?rp?rpnr?1p1.19题 n+m位由m个0,n个1组成的符号串,其中n≤m+1,试问不存在两个1相邻的符号串的数目。 解:m个0进行排列,留出m+1个空挡,任选n 个空挡放1,共有C(m+1,n)种方案.

3