组合数学第一章课后习题答案

2023年12月9日发(作者：常熟初一阳光数学试卷答案)

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题（王星）

解：

（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．2．若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.7题（王卓）

试证：

(n1)(n2)(2n)被2n除尽。

证明：因(2n)!2n!(2n1)!!

n(n1)(n2)(2n)n!(n1)(n2)(2n)(2n)!(2n1)!!

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

1．8题（王振华）

求10和20的公因数数目。

解：

因为10404030n240*540240*530*510

306030

202*5240*220*530

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

2a*5b,0a40,0b30

根据乘法法则，能除尽它的数个数为

41*31=1271

1.9题（王居柱）

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

20annbn证明：设有 , , 则一定有表达式nab，

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

又当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,…。

22由假设对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),并给予组合解释.

证：

(n1)!r!(nr1)!(r1)n!

(r1)r!(nr1)!(r1)n!(r1)!(nr1)!(r1)C(n,r1)nC(n1,r)n所以左边等于右边

组合意义：

等式左边：n个不同的球，先任取出1个，再从余下的n-1个中取r个；

等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。

所以两种方案数相同。

1.12题（李拂晓）

证明等式：kC(n,k)n2k1nn1

证明：

nn1n1n1n1等式左边nk1nk1nsk1k1s0n[C(n1,0)C(n1,1)C(n1,n1)]

nn2n1右边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}

总的组合数为：

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2,n2)}C(n,n2){C(2,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至中0出现的次数。

解：当第一位为0时，后面6位组成的数可以从1-，共个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数为：+99991+99901+99001+90001+1=。

1.16题（陈兴）

n个相同的球放到r个不同的盒子里，且每个盒子里不空的放法。

解：如果用“O”表示球，用“|”表示分界线，就相当于用r-1个“|”把n个“O”分成r份，要求是每份至少有一个球。如下图所示：

00|||00000|……

对于第一个分界线，它有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.17题（顿绍坤）

n和r都是正整数，而且rn，试证下列等式：

p(b)p(a)(c)(d)nrnrnpn1r1(nr1)nnrpnnr1pnrpn1r,rnr1

p(e)pn1rpnrrpnr1n1rr!r(ppn1r1prr1)解：

(a)

npn1r1nn(n1)!n!(nr)!(nr)!pnr等式成立。

n!n!(b)

(nr1)p(nr1)r1(nr1)!(nr)!(c)

(d)

pnr等式成立。

nnrpn1rn(n1)!n!nr(nr1)!(nr)!pnr等式成立。

pnrrpnr1n!n!n!(nr1)n!(n1)!n!rrn!rr(nr)!(nr1)!(nr1)!(nr1)!(nr1)!(n1)!(n1r)!nr1pn1r(e)利用(d)的结论可证明本题。

r!r(pnpn1r1n1r1r1r1prr1)pppprrrrr1rprprprrr1r1r1r1prprprrrprr1n1r1nr1r2r1prprpr1pr2rn1r1rpnr1

n1r1.18题（高亮）

8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？

解：

要求空盒不相邻，这样球的位置共有8种

5而不同标志的球的排列有p55!

所以共有8*5！种排列。

8种排列如下两类

因为要求空盒不相邻，途中1代表球

a) 1 1 1 1

b) 1 1 1 1

在a)中 剩下的一个球有四种位置

b)中剩下的一个球也有四种位置

两者合起来一共有8种

1.19题（李拂晓） n+m位由m个0，n个1组成的符号串，其中n≤m+1,试问不存在两个1相邻的符号串的数目。

解：

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

1.20 题（孙明柱）

甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志占5人，试问有多少中方案？

解：

1.甲单位出4个男同志，乙单位出1个男同志，从乙单位出2个女同志

C(10,4)*C(15,1)*C(10,2)=

2. .甲单位出3个男同志，乙单位出2个男同志，从甲单位出1个女同志,从乙单位出1个女同志。C(10,3)*C(15,2)*C(4.1)*C(10,1)=

3. .甲单位出2个男同志，乙单位出3个男同志，从甲单位出2个女同志.

C(10,2)*C(15,3)*C(4,2)=

1+2+3即为所求，总的方案数为

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.22题 （王居柱）

求图1-22中从O到P的路经数:

(a) 路径必须经过A点;

P

(b) 路径必须过道路AB;

(c) 路径必须过A和C

C

(d) 道路AB封锁(但

A B

A,B两点开放)

解: (a)分两步走O(0,0)→A(3,2)

A(3,2)→P(8,5)，根据乘法法则:

3235N23560

 (b)分两步走O(0,0)→A(3,2),B(4,2)→P(8,5)，根据乘法法则: 3243N23350

 （C）分三步走 O(0,0)→A(3,2), A(3,2)→C(6,3)，

C(6,3)→P(8,5)，根据乘法法则:

323122

N212240

 （d）AB封锁路径数加必经AB路径数即O(0,0)→P(8,5)的所有路径数有加法法则可得：

N5231287350937

1.23题（王振华）

令s={1,2,…,n+1},n≥2,T={(x,y,z)|x,y,z∈s, x

583243n1n1|T|k22

k123n证明：要确定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取值共有12…nn222kk1n2种可能。故|T|k2。

k1(2)由x

①x=y

2②x

3③y

3所以满足题意的x,y,z的组合数为n1n1n1n1n1++＝2。

23323n1n12k2。证毕。

k123n由于这两种方法是等价的，故可得|T|1.24题（王卓）

A={(a,b)|a,b∈Z,0≤a≤9,0≤b≤5},

(a) 求x-y平面上以A作顶点的长方形的数目。

解：如图，

(a,b)

从图中可以看出，对于x-y平面上满足题意的任一顶点A(a,b),除它本身以外，横坐标取值有9种可能，纵坐标取值有5种可能。顶点A(a,b)与和它不在同一水平线或垂直线上的任一点(x,y)均可构成一个长方形。故满足要求的长方形的数目为9×5=45个。

(b) 求x-y平面上以A作顶点的正方形的数目。

解：如下图，网格左边是b的取值，下面是a的取值。网格里是x-y平面上对应每个顶点A(a,b)所得的正方形的数目。

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*C102 225

c：有着五个点的两个点：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.26题（周英华）

S={1,2,……，1000}，a,b∈S,使ab≡0 mod 5,求数偶{a,b}的数目

解：

根据题意，ab可以整除5，

2*C（200，1）*1000=

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）=

C(5,1)*C(6,2)*C(5,2)*P(4,2)*7！

1.28题（王丹竹）

k和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数。

解：

若每个圆桌的的人数相等，则每个桌子有n个人。因为圆周排列的个数为因此本题的结果为prnr

(kn)!(kn)!k。

nnnn1.29 题（王星）

从n个对象中取个r做圆排列，求其方案数目。1<=r<=n 解：

c(n,r)*Q（r,r）

=c(n,r)*(r-1)!

1．30题（宗传玉）

（1）r1， 1rn；

r=n/rnn1（2）

r=（n-r+1）/rr1, 1rn；

nn(3)

rr=n/(n-r)nn1 , 0rn；

解：

（1）：

rn!/(r!(n-r)!)

nn1 n/rr1=n/r*((n-1)!/((r-1)!(n-r)!))= n!/(r!(n-r)!)=上式

所以两式相等

（2）：

rn!/(r!(n-r)!)

nn(n-r+1)/rr1=（n-r+1）/r*((n!)/((r-1)!(n-r+1)!))= n!/(r!(n-r)!)=上式

所以两式相等

（3）：

rn!/(r!(n-r)!)

nn/（n-r）n1=（n-1）!/(r!(n-r-1)!))= n!/(r!(n-r)!)=上式

r所以两式相等

1.31题（宗传玉）

证明：由 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.32题（王星）

解：

满足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.33题（王丹竹）

已知r，n，k都是正整数，rnk，将r个无区别的球放在n个有标志的盒子里，每盒至少k个球，试问有多少种方案？

解：

首先从r个球中取出nk个球放入n个盒中，因为球是无区别的。因此只有一种排列方案。剩下的球，每个球放的时候都有n中可能。因此方案数为n(r-nk).

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=P1a1 P2a2。。。Pnan，P1，P2，。。。Pn是n个不同的素数，每个能整除尽数n的正整数都可以选取每个素数Pi从0到ai次，即每个素数都有ai+1种选择，所以能整除n的正整数的数目为(a1+1)(a2+1)。。。(ai+1)个。而设M=N2=P12a1 P22a2。。。Pn2an，能被(2a1+1)(2a2+1)。。。2(ai+1)个整除。所以一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数。

1.37题（王卓）

.给出

nrn1r1n2r2nmrmnr1+++…+m0m11m220m=m

的组合意义。

解： Y

B（m,n+r+1-m）

P’

P(k,r)

0 k m X

如上图所示

rkk表示（0，0）点到P点的路径数；

P点到P’点只有一步；

nmmknkmk=mk表示P’点到B点的路径数;

nr1m表示（0，0）点到B点的路径数。

所以0点到B点的路径由0点到P点再从P点到P’点，最后从P’点到达B点。

M0+rknkk*1*mk=0Mnrn1r1n2r2m0+m11+m22+…nmrmnr1=

0mm1.38题（王振华）

rr1r2nn1给出rrrrr1的组合意义。

解：

设A={a1,a2,….,anr1 ,……,an1 },从A中取r+1个元素组合成C，考虑以下n-r+1种情况：

n（1）

a1∈C，则A需要从A{a1}中取r个配合，构成C，共r种可能

（2）

a1c，a2c,则需要从A{a1,a2} 中取r-1个，加上a2构成C，共中可能

……

(n-r)a1,a2,...,anr1C，anrC，则需从A{a1,a2,...,anr}中取r个组合，再加上n1rr1anr构成C，共r种可能。

r(nr1)a1,a2,...,anrC,这时只有r=1种可能。

故r+…+r+r=r1

r+r+（法二）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 题（王居柱）

n证明(m,0)C(m,n)+C(m,1)C(m-1,n-1)+…+C(m,n)C(m-n,0)=2C(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)C(m-1,n-1)=C(m,n)C(n,1)

…

C(m,n)C(m-n,0)=C(m,n)C(n,n)

由上知：

左边=[C(n,0)+C(n,1)+ … +C(n,n)]C(m,n)

由(xy)n=C(n,0)x +C(n,1)xn1y+C(n,2)xn2y2+…+C(n,n)yn

令x=y=1

可得 C(n,0) +C(n,1) +C(n,2) +…+C(n,n)=2

左边=2C(m,n)=右边

命题得证。

1.40题（王健）

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

解：

圆排列:共有P(n,r)/r种不同的方案。

1.41 题（孙明柱）

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

解：

利用“字典序法”生成下一排列的算法 ，计算该排列的对应序号，

生成已知排列序号算法：

设 int M为每一排列的对应序号初始时： P1_P2_...Pi-1_Pi_Pi+1_...Pn_ (其中P1_

I. 满足关系式Pj-1

的j的 最大值，设为i , 即i=max{ j | Pj-1

nnn1n2r1rn1nnII. 满足关系式Pi-1

的k的 最大值，设为j, 即j=max{ j | Pi-1

III. 使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，

ELSE M=M+1 GOTO Ι

（2）给定序列号计算排列算法：

设 Int M为每一排列的对应序号，M=N （N为给定序号）

设 Int K为循环次数

FOR （K=1；K++；K <=N ）

{

满足关系式Pj-1

的j的 最大值，设为i , 即i=max{ j | Pj-1

满足关系式Pi-1

的k的 最大值，设为j, 即j=max{ j | 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.42题（李拂晓）

1：给定排列求相应序号：

设 Int I为每一排列的对应序号 I=1 （初始化）

假定A[1：n]和E[2：n]；D[2：n]；B[1：n]都是整数数组，其中B[1：n]为给定序列 S1： A[1]1 i从2到n作 始 A[i]i，D[i]i，E[i]1 终；S2： q0； 判断A[1：n]是否与B[1：n]相等 若相等则输出I值 否则II1；S3： k从n降到2作 始 D[k]D[k]E[k]; pD[k]; 若 pk 则作E[k]-1; 否则作 始 若p0 则作 始 E[k]1, qq1 终 否则作

始 ppq; rA[p]; A[p]A[p1];

A[p1]r; 转S2 终 终

终

2：给定序号求相应排列：

设 Int I为每一排列的对应序号 I=1 （初始化） M为给定序列号假定A[1：n]和E[2：n]；D[2：n]；都是整数数组

M=N S1： A[1]1 i从2到n作 始 A[i]i，D[i]i，E[i]1 终；S2： q0； 判断 I 是否与 M 相等 若相等则 i从1到n输出A[i]； 否则II1；S3： k从n降到2作 始 D[k]D[k]E[k]; pD[k]; 若 pk 则作E[k]-1; 否则作 始 若p0 则作 始 E[k]1, qq1 终 否则作

始 ppq; rA[p]; A[p]A[p1];

A[p1]r; 转S2 终 终 终

（a） 由给定排列生成其下一个排列的算法

从排列 pp1p2pn生成下一个排列S1： 若在 pp1p2pn 中无一处于活动状态则停止。 求处于活动状态各数中的数值最大者，

S2：S3： 比 m 大的数一律改变箭指头向的 转；S1。1.43题（高亮）

对于给定的正整数N，证明，当K=

（N-1）/2或（N+1）/2， 若N是奇数

N/2， 若N是偶数

时，C(N,K)是最大值。

证明：

要证明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）/n >1

设为m， m 和它箭头所指一侧数相互邻换位置。当n为奇数,k=(n-1)/2时

（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）取最大值

1.44题（顿绍坤）

（a）用组合方法证明（b）证明(3n)!(2n)!和都是整数。

2n2n3n(n!)(n)!2n1是整数。

解：

(a)

①方法一：

因为：

(2n)!2nn!(2n1)!!

所以

(2n)!2nn!(2n1)!!n!(2n1)!!

nn22n!(2n1)!!是整数，因此(2n)!是整数。

2n方法二：

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

2n②若有3n个不同的球,放入n个不同盒子,每个盒子放三个，这个方案应该是整数。对这3n个球进行排列得到方案数为(3n)!。而把3个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了3！次。得到3n个不同的球放入n个不同的盒子里，每盒三个的方案数(3n)!(3n)!nn

n(3!)32(b) 有n个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n2)!/(n!)n是整数。另外由于n个盒子相同，放入不同的盒子是没有区别的，应该把n个盒子的排列数n!除去。

因此得到(n2)!/(n!)n+1是整数。

1.45题（陈兴）

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

解：有n个相同就有n个不相同

取n个不相同和0个相同的为C(n,n), 取n-1个不相同的球和1个相同的球为C(n,n-1)，2等等。

所以总的方案数为

Cn,0Cn,1Cn,n2n

(b) 在3n+1个球中，有n个相同。求从这3n+1个球中选取n个的方案数

方法同上，方案数为

C2n1,0C2n1,1C2n1,n

由于C(2n+1,0)=C(2n+1,2n+1),… ,C(2n+1,n)=C(2n+1,n+1)

C2n1,0C2n1,1C2n1,2n122n1

则

12n1C2n1,0C2n1,1C2n1,n222n

21.46题（陈兴）

证明在由字母表{0,1,2}生成的长度为n的字符串中.

(a)0出现偶数次的字符串有个；

(b)，其中.

证：(a)归纳法：当n=1时,0出现偶数次的字符串有(31+1)/2=2个(即1,2),成立。

假设当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出现偶数次的字符串数，两边显然相等。

1.47题（顿绍坤）

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

解：

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

所以总的方案数为1.48题（高亮）

C(m,2n)C(2n,n)3n0q(m2n)mq

2在由n个0及n个1构成的字符串中，在任意前k个字符中，0的个数不少于1的个数的字符串有多少？

解：

转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1。

1.49 题（李拂晓）

在1到n的自然数中选取不同且互不相邻的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)，且只有当n≥2k-1时,g(n,k)>0,否则g(n,k)=0,可给定初始值g(2k-1,k)=1,g(2k-2,k)=0.

1.50题（孙明柱）

(1)在有5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个？

(2)在有m个0，n个1组成的字符串中，出现01或10的总次数为k的字符串，有多少个？

解：

(1)、先将5个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的前面。（类似）。

由1和2得：3*C43*C430

(2)、m个0产生m-1个空当。

若k为偶数时：

要得到出现“01”与“10”总次数为k，可以先按上题中1的情况讨论，则在m-1个空当中21k2。分别插入个1即可，也就是Cm1剩下的1如何插入的问题与书P20页的定理1.2类似(在2n个不同元素中取r个允许重复的组合，其组合数为（C（n+r-1,r)），在这里无区别的球的个数也就是剩下的1的个数（即n-kk），盒子的个数也就是插入到m-1个空当中的1的个数(即2kkknnk22C)，则得出剩下的1的插入方法有n1。即第一种情况的总的插入方法为：Cm1*Cn12。

2k22m1k222。

n1n同理可得，按2的情况讨论后的第二种情况的总的插入方法为：C*C1和2得总的插入方法为：C若k为奇数时：

k2m1*Ck2n1nCk22m1*Ck222n1n。

则必有且只有一个1插入字符串的头或尾，剩下的1按照1的方法插入，只有这样才能使k为奇数。

所以插入的总方法为：2*C1.51 题（王健）

从N={1,2,…,20}中选出3个数，使得没有两个数相邻，问有多少种方案？

解：

相当于从N={1,2,…,20}个数中取3个作不相邻的组合，故方案数为C(20-3+1,3)=C(18,3)种

1．52题（王居柱）

从s={1,2,n}中连取k个数，使之没有两个数相邻，求不同方案数。

解：

在n个数中选k个数，使之没有两个数相邻，相当于在n-k+1位置中插入k个数，k个数中没有俩个数相邻。有Cnk1kk12m1*Ck12。

n1n(nk1)!种方案。

k!有定理1.4直接可得。

1.53题（王振华）

把n个无区别的球放进有标志1，2，…，n的n个盒子中，每个盒子可放多于一个球，求有多少种方案？

解：

把n个无标志的球放进n个有标志的盒子中，每个盒子允许多于一个球是允许重复的组合所以是nn12n1=

nn1.54题（王卓）

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

解：

相当于n个0排列后,使m个1做不相邻的插入，共产生n+1个位置.第一个1插入有n+1种情况，第二个是n种情况…第m个1插入就有n-m+1种情况。

所以是（n+1）（n）（n-1）…（n-m+1），即此题解为pn+1

m。

1.55题（翟聪）

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

证明：

根据所有偶数位置上的数字及所有奇数位置上的数字分别相加，再求出两个和的差，如果所得的差能被11整除，那么这个整数必能被11整除。

例如，偶数位上是：2，4，3，1。奇数位上是：1，3，4，2 因为对称数是偶数个，所以偶数为相加与奇数为相加的和是相等的，他们的差是零，而零能能被任何数整除，所以原题成立。证毕。

1.56 题（周英华）

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

解：

根据题意，两个女人之间坐1个男人的方案数Q (n,n)* P(n,n)

无两个女人并坐的方案数Q (n,n)* P (n,m)

1．57 题（孔令琦）

n个人分别沿着两张圆坐下，一张r人，另一张个n-r人，试问有多少种不同的方案数？

解：

C（n,r）*(r-1)!(n-r-1)!

1.58题（王丹竹）

一圆周上n个点标以1,2,,n。每一点与其它n-1个点连以直线，试问这些直线交于圆内有多少点？

这些直线交于圆内有C（n,4）个点

因为四个点连在一起构成一个四边形，这个四边形的对角线相交

于一个点，求这些直线交于圆内多少点就是求这些点能构成几个

四边形，即转化为从n个点取出四个进行组合