组合数学第一章答案

组合数学第1章答案

１.１ 从?1，2，???，50?中找两个数?a,b?，使其满足

（1） |a?b|?5；

（2）|a?b|?5

a?b?5a?b??5解：（1）根据|a?b|?5 可得 或 则有

45种45种 共有90种。

（2）根据|a?b|?5 得 {b?5?a?b?5a,b?(1,2,???,50)

则：当b?5时，有 b?1 ， 1?a?6， 则有 6种 b?2 ， 1?a?7， 则有7种 b?3 ， 1?a?8， 则有8种 b?4 ， 1?a?9， 则有 9种 b?5 ， 1?a?10， 则有10种 当5?b?45时，有 b?6 ， 1?a?11， 则有 11种 b?7 ， 2?a?12， 则有 11种

. . . . . . . . . b?45 ， 40?a?50， 则有11种 当45?b?50时，有 b?46 ， 41?a?50， 则有 10种 b?47 ， 42?a?50， 则有 9种 b?48 ， 43?a?50， 则有 8种 b?49 ， 44?a?50， 则有 7种 b?50 ， 45?a?50， 则有 6种

故：共 40?11?2(10?9?8?7?6)?520种

1.2 （1）先把女生进行排列，方案为5！，然后把女生看成1个人和7个男生进

行排列，总方案数为5！×8！

（2）女生不相邻，则先把男生进行排列，方案为7！再把女生插入男生之间

的8个空位种的任意5个，总方案数为7！×P85

（3）应该是A 女生x 女生y 女生z B,或是B女生x 女生y 女生z A的形

式，从5个女生中选出3人进行排列，方案为P53，考虑A,B可以换位，方案为2×P53，然后把这个看成一个整体，和剩下的2个女生，5个男生，一共7个人进行排列，总方案数2×P53×8！

1.3 m个男生,n个女生,排成一行,其中m,n都是正整数,若 （a）男生不相邻（m≤n+1）；

（b）n个女生形成一个整体； （c）男生A和女生B排在一起； 分别讨论有多少种方案。 解：

(a)n!p(n+1,m) (b)(m+1)!n! (c)2(m+n-1)!

1．4 26个英文字母进行排列，求X和Y之间有五个字母的排列数？ 解:排列数为C(24,5)*5！*2*20！

1.5 求3000到8000之间的奇整数的数目，且没有相同的数字。 解：设四位数为n3n2n1n0.

由已知可知，n3只能取，3，4，5，6，7，8，n0只能取1,3,5,7,9. 分以下两种情况讨论：

1.当n3取3，5，7的时候，由于是不能重复的，所以n0只能有4种选择，而剩下的n2,n1分别有8，7种选择。 所以符合条件的数，根据乘法原理有：

3*4*8*7=672.个

2.当n3取4，6，8时，由于是不能重复的,所以n0有5种选择，而剩下的

n2,,n1分别有8，7种选择，所以符合条件的数，根据乘法原理有： 3*5*8*7=840个

所以综上所述，符合条件的数，根据加法原理共有： 672+840=1512个 1.6

1*1!+2*2!+3*3!????+(n-1)*(n-1)! 根据公式得

1*1!+2*2!+3*3!????+(n-1)*(n-1)!=n!-1

1.7 试证 （n+1）(n+2)…(2n)被2k除尽。 证明：

(n?1)(n?2)...(2n)??2(2n)!n!?2n(2n?1)!n(n?1)!2?2(2n?1)!(n?1)!?...

(2n?2)(2n?1)(2n?3)!(n?1)(n?2)!n?2(2n?1)(2n?3)!(n?2)!?2(2n?1)(2n?3)...3所以（n+1）(n+2)…(2n)能被2k除尽。

1.8 求1040和2030的共因数的数目. 解: 10 40=2 40 * 5 40

20 30=260 * 5 30

∴ 1040和2030的公因子有40*30=1200 个

1.9 试证n的平方的正除数的数目是奇数 答案：因为n的平方一定是两个数的乘积，一定是两个不同的数的乘积或唯一的一个相同的 数的乘积。例如，16可以是1*16，2*8或4*4，前面的都是成对出现的，只有4是一个 数，所以他们的和一定是奇数。 1.10 证明任一正整数n可唯一地表示成如下形式： n=?ai?i!, 0?ai?i, i?1

i?1证明：对n用数学归纳法

① 当n=0,1时，0=0?1! , 1=1?1!。命题成立。 ② 假设对于小于n的非负整数，命题成立。

③

0?n?k!

?(k对于

?1k)?n

!，

k ?设

?kk!?n?(，k?k?即

?k?k?由②，对n?k!命题成立。设n?k!?0?ak?k?1k?ai?1i?i!，其中0?ai?i，

(原因是0?n?k!?k?k而!不能等于k?k!)，那么

k?1n??ai?1i?i!?k!??ai?1i?i!?(ak?1)?k!，其中0?ak?1?k，命题成立。

再证唯一性：

kki设n??ai?1?i!??bi?1i?i!，不妨设aj?bj，j?min{i|ai?bi}，即

??3!?b1?1?b!2?2?b3!??， 3?!?a1?1!?a2?2!?a3假设a1?b1，a2?b2，a3?b3，则j=3。那么，因为ai与bi前j项相等，上式两边均减去前j项，即?aii!?i?j?bi!，即

ii?jajj!?aj?1(j?1)!?aj?2(j?2)!??bjj!?bj?1(j?1)!?bj?2(j?2)!?

将上式两边都除以(j?1)!，得

ajj!(j?1)!?aj?1?aj?2(j?2)??bjj!(j?1)!?bj?1?bj?(2j?2)?

可以看出，上式的余数为ajj!=bjj!与假设矛盾。因此ai是唯一的 1.11求证：nC(n-1,r)=(r+1)C(n,r+1) 证明：

左边=C(n,1)C(n-1,r) 右边=C(r+1,1)C(n,r+1)

=C(n,1)C(n-1,r+1-1) =C(n,1)C(n-1,r) =左边

所以等式成立。

n1—12 试证: 证明:

(1+

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

=C(n,0)+C(n,1)x+C(n,2)x2+?+C(n,n)xn

两边求导,并令x=1代入

n(1+1)n?1=C(n,1)+C(n,2)x+C(n,3)x2+? +C(n,n)xn?1

nn2

n?1??kC(n,k)

k?1组合意义:

设有n个不同的小球,A,B两个盒子,A盒中恰好放1个球,B盒中可放任意个球.有两种方法放球:

第一种: 先从n个球中取k个球(k≥1),在从k中挑一个放入A盒,方案数共

n为?kC(n,k),其余放入B盒.

k?1第二种: 先从n个球中任取一球放入A盒,剩下n-1个球每个球有两种可能,要么放入B盒,要么不放,故方案数为n2n?1, 显然相等.

1.13：有N个不同的整数，从中取出两组来，要求第一组的最小数大于第二组的最大数。

解：本题求取两组数的取法。

我们首先从N中去M个数（2<=M<=N）,因为M个数是不同的，所以存在一个递增的序列A=a1,a2,a3,a4……aM (a1

1.14 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从一个特定引擎开始有多少方案？

解： 设6个引擎分别为1、2、3、4、5、6

不失一般性，我们把1、2、3放在第一排，4、5、6放到第二排。 由题意知从一个特定引擎开始，不妨设从1开始，那么 （1）1开启之后，下一个开始点有4、5、6三种选择 （2）第二排的一个开启之后，下一个开始点有2，3两种选择 （3）然后第一排，第二排剩下俩，那么有两种选择 （4）然后第一排只剩一个，第二排只剩一个，所以就剩一种选择 所以，由乘法法则 方案数=3×2×2×1×1=12

1.15试求从1到1000000的整数中，0出现了多少次？ 解：先考虑1到99 9999.

个位为零的整数出现99999×1次 为：10—999990 十位为零的整数出现9999×10次 为：101—999909 百位为零的整数出现999×100次 为：1000—999099 千位为零的整数出现99×1000次 为：10000—990999 万位为零的整数出现9×10000次 为：100000—909999 而100 0000本身有6个零

所以从1到1000000的整数中，0出现的次数为：

99999×1+9999×10+999×100+99×1000+9×10000+6=488895

1.16 n个完全一样的球放在r个有标志的盒子里面?n?r? ，无一空盒，问有多少种方案？

解：r个盒子无一空盒，说明先要从n个球中取出r个先放每个盒中一个； 余下n-r个无标志的球，放入r个有标志的盒子中，根据定理可以得出 结果是C?r?n?r?1,n?r??C?n?1,n?r? 。

1.17 n和r都是正整数，而且r?n，试证下列等式 1) prn?nprn??11 2) prn?(n?r?1)prn?1 3) prn?nn?rprn?1,r?n

4) prn?1?prn?rprn?1

5) prn?1?r!?r(prn?1?prn??11????prr?1)

的排列数等于多少？

解：要求y必须在两个x之间，所以符合要求的排列必须有结构“xyxyx”，把“xyxyx”看作一个元素，与a,b,c,d,e,f,排列排列数等于6！。

1—33 已知r,n,k都是正整数,r≥nk,将r个无区别的球放在n个有标志的盒子里,每盒至少k个球,试问有多少种方案?

解: ①先保证每一个盒子至少k个球,因为球无区别,把n个不同盒子每一个盒子放k个球.共kn个.

②问题转化为将(r-nk)个小球放入n个不同盒子,每个盒子可以放任意个球,可以有空盒,根据可从复组合定理可得共(n+r-nk-1,r-nk)=(n+r-nk-1,n-1)

1.34在r，s，t，u，v，w，x，y，z，的排列中求y居于x和z中间的排列数。 解：一共9个位置，y只能放到2到8中间，当x放到第一个位置，y放到第二个位置，其他全排列有7！种方法，第一个位置也可以放z，共有2*7！种方法。y放到第三个位置，y前x有两种选择，y后z有6种选择，其他全排列，所以方法有2*6*6！，总方法有2*2*6*6种方法，以此类推算到y在第5个位置因为后边是对称的。

总数=2*（7！+2*6*6！+3*5*6！+4*4*6！） =72000

1．35 凸十边形的任意三条对角线不共点。试求这凸十边形的对角线交于多少个点？

解： 根据题意，每4个点可得到两条对角线，1个对角线交点，从10个顶点任取4个的方案有C(10,4)种，即交于210个点。

1.36 试证明一个整数是另一个整数的平方的必要条件是除尽它的数的数目是奇数。

答案：

由：

n=p1p2p3..............，其中

a1a2a3p1,p2是质数，a1,a2....是正整数。

则n的因子数有(a1+1)(a2+1)(a3+1)????个。 得 n2=p12a1p22a2p32a3..............，因为(2a1+1),(2a2+1),(2a3+1)???..

都是奇数，

所以 n2的因子数为(2a1+1)(2a2+1)(2a3+1)??.个，也是奇数个。

1.37 给出

?n??r??n?1??r?1??n?2??r?2??n?m??r?m??n?r?1?????????????????????????m?m??0??m?1??1??m?2??2??0??m??? 的组合意义. y 解: A(-1,m) m B(m-n,m)

. . . . . .

C(-r-1,0) -r-1 -1 0 m-n

可看作是格路问题:左边第i项为从点C到点(-1,i)直接经过(0,i)的路径,

再到点B的所有路径。左边所有项的和就是从C点到B点的所有路径数即为右边的意义.

1.38 给出??r????????r?r??r?1??r?2??n??n?1???????...???r??r?????r?1??的组合意义。 ???????解：设A??a1,a2,...,an?r?1,an?1?，从A中取r+1个元素组合成C，考虑以下n-r+1种情况：

（1）a1?C，则A需从A\\?a1?中取r个与a1配合，构成C，共????中可能。

?r??n?（2）a1?C,a2?C，则需从A\\?a1,a2?中取r个，加上a2构成能。

?n?1??C，共??r?种可??（n-r）a1,a2,...,an?r?1,?C,则需从A\\?a1,a2,...,an?r?中取r个组合，再加上a1构成

?r?1??C，共??r???种可能。

?r??r?（n-r+1）a1,a2,...,an?r?1,an?r?C,这时只有????=1种可能。

故??r????????r 1.39

?r??r?1??r?2??n??n?1???????...???r??r?????r?1?? ???????证明:

证：组合意义,右边：m个球,从中取n个,放入两个盒子,n个球中每个球都有两种

放法,得到可能的方案数。左边：第i项的意义是一个盒子中放i个,另一个盒子放n-i个,所有的方案数相加应该等于右边。

n左式＝n?C(m,k)C(m?k,n?k)k?0??k?0nm!k!(m?k)!(m?n)!(n?k)!m!?n!?(m?k)!??k?0nk!n!(m?n)!(n?k)!m!?n!

??k?0n(m?n)!n!k!(n?k)!n!k!(n?k)!?C(m,n)??k?0n?2C(m,n)?右式证毕。

1.40 从n个人中选出r个围成一个圆圈，问有多少种不同方案。

解：首先从n个人中选出r个有C(n,r)种方案，r个人进行一个圆周排列， 根据圆周排列公式，共有r!\\r种方案，既(r-1)!种方案， 所以根据乘法法则，一共有C(n,r)*(r-1)!种方案。

1.41 分别写出按照字典序，由给定排列计算其对应序号的算法及由给定序号计算其对应的算法。

解：生成所有排列的数组A[][]： S1. A[0][]<-S2. j<-0;

j从0到n，若pS3. i = max{ j | pj?1j?1pp...p<-12?N，LEN=1；

12n?p,则退出；

j?p}；

jS4. h = max{k | pi?1?p}；

kS5.将

和i?1ph 互换的

'1pp...12'n'1'n；

S6.A[LEN][]<- S7.将

''pp...p,LEN++；

12'1''12nip和p互换，得pp...p...p；

inS8.A[LEN]<-

pp...p...p, LEN++,转到S2;

12ni'1''给定排列计算其对应序号的算法 S1. 输入

pp...p；

12nS2.j<-0,j从0到LEN 若A[j][]==

pp...p，则输出j，退出；

12n 否则j++；

由给定序号计算其对应的算法 S1.输入序号j；

S2.输出A[j][]，退出；

1.42（a）按照习题1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法。 解：

S1.若p1p2?pn没有数处于活动状态则结束。

S2.将处于活动状态的各数中值最大者设为m，则m和它的箭头所指一侧相邻的数互换位置，而且比m大的所有数的箭头改变方向，即—>改为<—，<—改为—>。转S1。

（b）写出按照邻位对换法由给定排列生成其下一个排列的算法。 解：

S1.A[i]<—1； S2.i从2到n做

始A[i]<—i，D[i] <—i, E[i] <—-1终； S3.q<—0 i从1到n输出A[i];

S4.k<—n;

S5.若k>1则转S6；

S6.D[k] <—D[k]+E[k],p<—D[k]; S7.若p=k则做E[k] <—-1,转S10； S8.若p=0 则做 始E[k] <—1,q<—q+1转S10终；

S9.p<—p+q，r<—A[p],A[p] <—A[p+1],A[p+1] <—i，转S3; S10.k<—k-1转S5.

1.43证明：考虑C(n,k)和C(n,k-1)进行比较。

C(n,k)/C(n,k-1)=(n-k+1)/k。

当k>n/2时,(n-k+1)/k<1,即C(n,k)

当k>n/2时,(n-k+1)/k>1,即C(n,k)>C(n,k-1)得到当k为最接近n/2的数时，C(n,k)取到最大值。

1.44 （1）用组合方法证明 （2）证明

(n)!2(2n)！（3n）!2n和

2?3nn都是整数。

?n!?n?1是整数。

证明：

（1）设有2n个不同的球放入n个不同的盒子里，每个盒子两个，这个方案数应该是整数。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了(2!)n次，得到的2n个不同球放入n个不同的盒子里，每盒两个的方案数为

(2n)!(2!)n，得证。同理，若有3n

个不同的球，放入n个不同的盒子里，，每个盒子3个球，重复的次数为(3!)n，故方案数为

(3n)!(3!)n?(3n)!(3?2)n?(3n)!3?2nn，得证。

（2）设有n2个不同的球，将他们放入n个相同的盒子，每盒n个球，这个

方案数应该是整数。由（1）可知，将n2个不同的球放入n个不同盒子的方案数为

(n2)!(n!)n，若为相同的n个盒子，则应把n个盒子的排列数去掉，即n！，故n2个

(n)!2不同的球放入n个相同的盒子，每盒n个球的方案数为

?n!?n?1，证毕。

1.45 （1）在2n个球中，有n个相同，求从这2n个球中选取n个的方案数。

（2） 在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数。

解：

（1）相当于从n个不同的小球中分别取出m个小球（0?m?n），再从n个不同小球中取出n-m个小球。则共有方案数：C(n,0)?C(n,1)?????C(n,n)?2n

（2）相当于从2n+1个不同的小球中分别取出个小球（0?m?n），再从n

n个不同小球中取出n-m个小球。则共有方案数：?C(2n?1,m)

m?0

1.46（1）证明：利用归纳法，当n=1时，0出现偶数次的实例是{1,2}，其中0

出现0次，而当n＝1时，3n＋1/2=2，是正确的。

假设当n＝k时是正确的，即0出现 3k＋1/2 次，计算0出现

k?0出现奇数次的方案为3奇数次的方案，因为总方案数为3k，

－3k＋1/2＝3k－1/2.

当n＝k＋1时，0出现偶数次的方案数是前k为出现偶数次，

第k＋1位是1或2，或是前k位出现奇数个0，最后一位是0.

总方案数为2×（3k＋1）/2＋3k－1/2＝3k?1＋1/2,正是所要证明的形式，所以0出现偶数次的字符串有3n＋1/2个。

n （2）证明：等式左边第一项表示n位中有0个0，用?0?表示，那么这n位

n只能取1或2，有2n种可能，所以方案为?0?×2n，最后一项为

当n中有最大偶数个0出现时的方案数，所以左边整体表示为n位字符串中0出现偶数次的方案数，右边也是0出现偶数次的方案数，左边＝右边，即证。

1.47 5台教学机器m个学生使用，使用第1台和第2台的人数相等，有多少种分配方案？ 解：

当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3(m-2n)。

m/2所以总的方案数为?C(m,2n)C(2n,n)3(m?2n).

x?0

1.48 在由n个0及n个1构成的字符串中，任意前k个字符中，0的个数不少于1的个数的字符串有多少？ 解：转化为格路问题,即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案

C(2n,n)-C(2n,n-1).

1.49 在1到n的自然数中选取不同且互不相邻的k个数，有多少种方案？ 解：根据不相邻组合的公式，共有C(n-k+1)种方案k。

1.50

(a)在5个0，4个1组成的字符串中，出现01或10的总次数为4的，有多少个? (b)在m个0，n个1组成的字符串中,出现01或10的总次数为k的，有多少个？ 解：(a)先将5个0排成一列：00000，1若插在两个0中间，“010”，则出现2个“01”或“10”;若插在两端，则出现1个“01”或“10”;要使出现“01”,“10”总次数为4，有两种办法：

(1)把两个1插入0得空当内，剩下的1插入1的前面。

(2)把1个1插入0得空当内，再取两个1分别插入两端，剩下的1插入1的前面。

故总方案数为C(4,2)·3+C(4,1)·3=30 (b)m个0产生m-1个空当，

若k为奇数,则必有且只有1个“1”插入头或尾,总方案数为

2C(m?1,k?12)C(n?1,n?k?12) kkk?22)C(n?1,n?k?22)

若k为偶数,总方案数为C(m?1,)C(n?1,n?)?C(m?1,22第一问，出现4个01或10，说明5个0被分成了3段，四个1被分成了两段，然后夹在一起形如001101100；或者5个0被分成了2段，四个1被分成了3段，然后夹在一起形如100100011。于是题目的考虑就变成了5个0如何拆分，4个1如何拆分。 答案是：

C(4,2)*C(3,1)+C(4,1)*C(3,2) 1.51 从N??1,2,...20?中选出3个数，使得没有两个数相邻，问有多少中方案？ 解：???n?r?1??20?3?1???=??????r??3=???18??种 ??3?

1.52 从S={1,2,…,n}中选k个数,使之没有两数相邻,求不同方案数.

解: ?

?n?k?1??k??

1.53 把n个无区别的球放进有标志1，2，3，????n的盒子里，每个盒子里可以放多余一个球，求有多少中方案。 答案：

相当于在n个不同的元素中取r个作允许重复的的组合，其组合数为c(n-k+1,r)

1．54 m个1，n个0进行排列，求1不相邻的排列数。设n>m

解： n个0进行排列，留出n+1个空档，任选m个空档放1，共有C(n+1,m)种方案。

第

1.55 偶数位的对称，即从左向右的读法与从右向左的读法相同，如3223。试证这样的数可被11整除。 证明：

对称数ABBA可以写成 A*103+B*102+B*10+A*100，且11MOD10=-1MOD11,用-1代替10

恰好方次是奇偶对应的。使原式相加等于0。

1—56 n个男人与n个女人沿一圆桌坐下,问两个女人之间坐一个男人的方案数,又m个女人n个男人,且m

解: ① n 个女人先沿圆桌坐下,这时正好有n个空. 即 (P(n,n)/n)n!=(n!n!)/n

② n个男人沿圆桌坐下,方案数为本P(n,n)/n=n!/n

女人往男人中的n个空插入为p (n,m).所以方案数为(p (n,,m)n!)/n

1.57：n个人分别沿着两张圆桌坐下，一张r个人，另一张n-r个人，试问有多少种不同的方案？ 解：按照本题的要求，先从n中选r个人进行圆排列的方案是C（n，r）×(r-1)!。剩下（n-r）个人再进行圆排列（n-r-1）！。根据乘法原理一共有C（n，r）×（r-1）!×（n-r-1）！。

1.58 一圆周上n个点标以1，2，…，n.每个点与其他n-1个点连以直线，试问这些直线交于圆内多少点？ 解：

x1xn x1xn xi

图a

图b

如题意可知，每个点i和其他n-1个点相连，可以引出n-1条直线，那么我

们首先求圆内的交点在与点1相连的直线上的个数。 如图a，对于任意一条直线（1，i），这条直线上与其他直线的交点数，必然等于（1，i）的左边点与（1，i）的右边点相连的边的总条数，总共有

?i?2??n?i?????? 11???? 条边，也就有这么多个交点

所以对于点1引出的所有边，边上的交点数总和为

n?1

?i?3?i?2??n?i?????? ?1??1? 与点1相连的直线上的交点个数都求出来了，就可以先把点1去掉，如图b，

计算剩下的n-1个点的直线的交点个数。 所以n个点一共是：

nm?1

??m?4i?3?i?2??m?i?????? ?1??1?nm?1

那么这些直线交于圆内??m?4i?3?i?2??m?i??????个交点 ?1??1?1.59 n和k都是正整数，设平面有n个点，其中每一点都存在k个点与之距离

相等。试证k满足

证明：当k=1时成立，101001000100001?1代表点，0代表单位距离

当k=i成立，1..101..1001..10001..100001..100000.. ,1..1表示有i个1

当k=i+1时，1?101?1001?10001?100001?100000?,同样也成立1?1表示有i+1个1

本文来源：https://www.bwwdw.com/article/599g.html