第1页 / 共61页
第2页 / 共61页
第3页 / 共61页
第4页 / 共61页
第5页 / 共61页
第6页 / 共61页
第7页 / 共61页
第8页 / 共61页
组合数学 第4版(卢开澄)答案.pdf
组合数学 双卢 答案
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）先取两个男生和 3 个女生做排列，情况如下：
C（8，5）×7！×5！
A，B 之间共有 3 个人，所有的排列应为 P6=C(5,3)*3!*8!*2
A，B 之间共有 4 个人，所有的排列应为
6. 若 A，B 之间存在 0 个男生，
1．若 A，B 之间存在 1 个男生，
2．若 A，B 之间存在 2 个男生，A，B 之间共有 5 个人，所有的排列应为
3．若 A，B 之间存在 3 个男生，A，B 之间共有 6 个人，所有的排列应为
4．若 A，B 之间存在 4 个男生，A，B 之间共有 7 个人，所有的排列应为
5．若 A，B 之间存在 5 个男生，A，B 之间共有 8 个人，所有的排列应为
所以总的排列数为上述 6 种情况之和。
P1= C(5,1)*C(5,3)*4!*7!*2
P2=C(5,2)*C(5,3)*5!*6!*2
P3=C(5,3)*C(5,3)*6!*5!*2
P4=C(5,4)*C(5,3)*7!*4!*2
P5=C(5,5)*C(5,3)*8!*3!*2
1.3 题 m 个男生，n 个女生，排成一行，其中 m,n 都是正整数，若
)1
(a)男生不相邻
分别讨论有多少种方案。
+≤ nm
(
;
(b)n 个女生形成一个整体； (c)男生 A 和女生 B 排在一起；
解：(a) 可以考虑插空的方法。
n 个女生先排成一排，形成 n+1 个空。因为
1+≤ nm
正好 m 个男生可以插在 n+1 个空中，形成不相邻的关系。
则男生不相邻的排列个数为
n
pp
⋅
n
n
1+
m
+
(!
⋅ mn
(b) n 个女生形成一个整体有 n！种可能，把它看作一个整体和 m 个男生排在一起，则排列数有(m+1)!种可能。
因此，共有
(c)男生 A 和女生 B 排在一起，因为男生和女生可以交换位置，因此有 2！种可能，
A、B 组合在一起和剩下的学生组成排列有(m+n-1)！
(这里实际上是 m+n-2 个学生和 AB 的组合形成的)种可能。共有组合数为
种可能。
nm
−+
(!2
⋅
)!1
)!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 题 试证：
证明：因
(
)2
)(1
(
)2(
n
n
n
L+
+
2(!2
)!2(
!)!1
n
n
n
n
=
−
)(1
)2(
)2
n
n
n
+
+
L
=
2
n
被 2n 除尽。
(!
nn
+
)(1
n
+
2!
n
n
)2
L
)2(
n
=
)!2(
n
2!
n
n
=
2(
n
−
!)!1
1
因为(2n-1)!!是整数所以
(
n
+
)(1
n
L+
)2
)2(
n
能被 2n 除尽。
1．8 题 求 4010 和 3020 的公因数数目。
30
40
解：因为
=
=
10
5*2
40
它们最大公因子为
0,5*2
a
<=
根据乘法法则，能除尽它的数个数为 41*31=1271
5*5*2
40
10
40
40 5*2
30
0,40
<=
<=
<=
20
a
30
b
1.9 题 试证 2n 的正除数的数目是奇数。
证明：设有
a
0
< <
< <
,
n n b
a b
则 可知符合范围的 a 和b 必成对出现，所以为偶数。
又当 a=b=n 时，表达式 2n =a×b 仍然成立。 所以
, 则一定有表达式 2n
n
= × ，
2
=
5*2
60
30
=
5*2*2
40
20
30
转化为求 最大公因子 能除尽的整数个数，能除尽它的整数是
b
30
2n 的正除数的数目是“偶数 1+ ”为奇数。
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·j!+aj-1·(j-1)!+…+a1·1! =bj·j!+bj-1·(j-1)!+…+b1·1!,
∑
(
a
!
ii
≥⋅
!
j
=⋅
!
i
≥⋅
∑
∑
(
b
i
!
j
>
−
−
b
a
)
)
j
i
j
, 不妨设 aj＞bj,令 j=max{i|ai≠bi}
b
i
−
a
i
!
i
≥⋅
∑
(
b
i
−
a
i
)
!
i
⋅
矛盾，命题成立。
1.11 题 证明 nC(n-1,r)= (r+1)C(n,r+1),并给予组合解释.
证：
(
nC n
−
1,
r
)
=
n
(
n
! (
n
⋅
1)!
−
r
− −
r
=
1)!
(
1)
r
⋅
1)
+
⋅
! (
n
r
⋅
n
− −
!
r
(
r
+
=
1)!
(
r
+
(
r
+
1)! (
⋅
1)
n
!
n
⋅
r
− −
1)!
=
(
r
+
1)
( ,
C n r
+
1)
所以左边等于右边
组合意义：等式左边：n 个不同的球，先任取出 1 个，再从余下的 n-1 个中取 r 个；
等式右边：n 个不同球中任意取出 r+1 个，并指定其中任意一个为第一个。
所以两种方案数相同。
1.12 题 证明等式：
n
∑
k
1
=
kC
,(
kn
)
=
n
2
n
1
−
证明：
=
等式左边
n
∑
n
1
=
k
n
k
1
−
1
−
=
n
∑
n
1
k
=
n
k
1
−
1
−
=
1
n
−
∑
n
0
s
=
n
1
−
s
=
[
n C n
( 1,0)
−
( 1,1)
C n
+
−
L
+ +
( 1,
C n
]
1)
− − =
n
2
n
1
n
−
=
右边
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}
总的组合数为：
2
( ,1) { (
C n
C n
⋅
( ,
C n n
+
L
+
1,2)
1,1)
(
C n
−
−
+
+
L
( ,
2) { (2,1)
C
C n n
− ⋅
+
(
C n
+
1)
C
− ⋅
1,
n
−
(1,1)}
−
1)}
+
C n
( ,2) { (
C n
⋅
−
2,1)
+
(
C n
−
2,2)
+
L
+
(
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 个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？
解：要求空盒不相邻，这样球的位置共有 8 种。而不同标志的球的排列有
8 种排列如下两类。因为要求空盒不相邻，途中 1 代表球
5 =p
5
!5
。所以共有 8*5！种排列。
1
a)
b)
1
1
1
1
1
1
1
在 a)中 剩下的一个球有四种位置，b)中剩下的一个球也有四种位置，两者合起来一共有 8 种
( )
c
p
n
r
=
n
n r
−
p
n
1
−
r
,
r
<
n
n
( )
a
1.17 题 n 和 r 都是正整数，而且 n
p
p
p
p
p
p
( )
d
( )
b
( )
e
=
+
=
n
r
1
+
1
−
1
−
n
n
n
n
n
r
r
r
r
1
−
r
p
p
n
r
解：(a)
n
1
•=−
n
1
−
(b)
(
rn
+−
)1
p
n
r
1
−
r ≤ ，试证下列等式：
n
r
=
(
n r
1)
− +
p
r
(
n
!
= +
r
1
+
n
r
p
+
r
1
−
1
−
p
n
1
−
r
1
−
+
+L
p
r
r
)
1
−
等式成立。
r
!
n
rn
−
)1
•+−
(
)!1
n
−
(
)!
rn
−
(
rn
=
=
(
)!
n
r
=
p
!
n
rn
+−
(
(
)!1
n
−
rn
−−
=
(
)!1
!
n
rn
−
p
n
r
=
(
=
)!
)!1
!
n
rn
−
p
n
r
=
)!
等式成立。
等式成立。
p
n
1
−
r
=
n
rn
−
•
(
(c)
(d)
n
rn
−
p
n
+
r
r
p
n
r
1
−
=
!
n
(
n r
−
)!
r
+ ⋅
!
n
(
n r
− +
=
1)!
1)
!(
n n r
− +
1)!
(
n r
− +
r
+ ⋅
!
n
(
n r
− +
1)!
(
n
=
!
1)!
!
r n
n r
+ − ⋅ + ⋅
(
n r
− +
1)!
=
1)!
(
n
+
1
(
)!
n
r
+ −
=
1
n
p +
r
(e)利用(d)的结论可证明本题。
r
!
+
r
(
p
n
r
1
−
+
p
n
1
−
r
1
−
+
L
+
p
r
r
)
1
−
=
=
=
n
r
+
r
+
1
r
+
r
r
p
r
p
r
r
+
r
p
p
p
r
r
r
1
−
+
1
−
1
r
+
r
1
−
p
+
r
p
r
p
r
r
r
+
n
1
−
+
1
r
−
1
+
r
+
1
−
2
r
+
L
p
L
+
+
r
+
r
2
r
1
−
+
r
1
−
p
r
p
r
L
+
p
r
1
−
+
1
n
−
r
1
−
r
p
r
+
n
r
1
−
+
1
−
n
p
r
1
−
r
r
n
p
p
=
1
−
1
n
+
r
1.19 题 n+m 位由 m 个 0，n 个 1 组成的符号串，其中 n≤m+1,试问不存在两个 1 相邻的符号串的数目。
解：m 个 0 进行排列，留出 m+1 个空挡，任选 n 个空挡放 1，共有 C(m+1,n)种方案.
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.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
1.22 题 求图 1-22 中从 O 到 P 的路经数:
(b) 路径必须过道路 AB;
(a) 路径必须经过 A 点;
(d) 道路 AB 封锁(但 A,B 两点开放)
(c) 路径必须过 A 和 C
解: (a)分两步走 O(0,0)→A(3,2) A(3,2)→P(8,5)，根据乘法法则:
=N
23
+
2
×
53
+
3
=
560
P
C
A
B
(b)分两步走 O(0,0)→A(3,2), B(4,2)→P(8,5)，根据乘法法则:
=N
23
+
2
×
34
+
3
=
350
(c)分三步走: O(0,0)→A(3,2), A(3,2)→C(6,3), C(6,3)→P(8,5), 根据乘法法则:
=N
23
+
2
×
13
+
×
1
22
+
2
=
240
（d）AB 封锁路径数加必经 AB 路径数即 O(0,0)→P(8,5)的所有路径数有加法法则可得：
=N
85
+
5
−
23
+
2
×
34
+
3
=
1287
−
350
=
937
1.23 题 令 s={1,2,…,n+1},n≥2,T={(x,y,z)|x,y,z∈s, x
所以满足题意的 x,y,z 的组合数为 1
n +
2
+
n +
3
1
+
n +
3
1
n
＝ 1
+
2
+
2
n
+
3
1
。
由于这两种方法是等价的，故可得
|
T
|
=
k
1.24 题 A={(a, b)|a, b∈Z, 0≤a≤9,0≤b≤5}
n
∑
1
=
2
k
=
n
+
2
1
+
2
n
+
3
1
。证毕。
(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≡0 mod 5,求数偶{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*C102 225
由 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)
c：有着五个点的两个点：10*C52=100
1.27 题 6 位男宾，5 位女宾围一圆桌而坐，（1）女宾不相邻有多少种方案？（2）所有女宾在一起有多少种方案？（3）
一女宾 A 和两位男宾相邻又有多少种方案？
解 ：（1）若 5 位女宾不相邻，先考虑 6 位男宾围圆桌而做的方案数，然后女宾插入 Q（6，6）*6*5*4*3*2=86400
（2）把 5 位女宾看成一个整体，然后插入
（3）C（5，1）*C（6，2）*Q（8，8）=194000
C(5,1)*C(6,2)*C(5,2)*P(4,2)*7！
Q（6，6）*6*P(5,5)=86400
1.28 题 k 和 n 都是正整数，kn 位来宾围着 k 张圆桌而坐，试求其方案数。
pn
解：若每个圆桌的的人数相等，则每个桌子有 n 个人。因为圆周排列的个数为 r
r
因此本题的结果为
)!
(
kn
nn
⋅ L
n
(
=
kn
kn
)!
。
1.29 题 从 n 个对象中取个 r 做圆排列，求其方案数目。1<=r<=n
解：c(n,r)*Q（r,r）
=c(n,r)*(r-1)!
1.31 题 试证任意 r 个相邻数的连乘：(
n
+
1)(
n
+
2)
n r
+L
(
)
被 r！除尽.
5
证明：由 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！除尽。
n
1．30 题 （1）
r
=n/r
n
r
−
−
1
1
n
， 1 ≤ r ≤ n；（2）
r
=（n-r+1）/r
n
−1r
, 1 ≤ r ≤ n；(3)
n
r
=n/(n-r)
n 1
−
r
, 0 ≤ r ≤ n；
解：（1）：
n
r
=
n!/(r!(n-r)!)
n/r
n
r
−
−
1
1
=n/r*((n-1)!/((r-1)!(n-r)!))= n!/(r!(n-r)!)=上式
所以两式相等
（2）：
（3）：
n
r
n
r
=
=
n!/(r!(n-r)!)
(n-r+1)/r
n
−1r
=（n-r+1）/r*((n!)/((r-1)!(n-r+1)!))= n!/(r!(n-r)!)=上式 所以两式相等
n!/(r!(n-r)!)
n/（n-r）
n 1
−
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 之间应为 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!
r ≥ ，将 r 个无区别的球放在 n 个有标志的盒子里，每盒至少 k 个球，试问有
1.33 题 已知 r，n，k 都是正整数， nk
多少种方案？
解：首先从 r 个球中取出 nk 个球放入 n 个盒中，因为球是无区别的。因此只有一种排列方案。剩下的球，每个球
放的时候都有 n 中可能。因此方案数为 nk)
1.34 题 在 r,s,t,u,v,w,x,y,z 的排列中求 y 居于 x 和 z 中间的排列数
-(rn
.
解 ： 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)个整除。所以一整数是另外一整数的平方的必要条件是除尽他的数的
数目是整数。
n
m
mrmn
−
0
r
+
2
r
+
1
2
n
−
2
m
−
+
m
1
n
−
1
m
−
rn
m
的组合意义。
++
+…+
r
0
1
1
+
=
2
1.37 题 .给出
+
Y
解：
P’
P(k,r)
k
B（m,n+r+1-m）
m
X
表示（0，0）点到 P 点的路径数；
如上图所示，
0
k
r
+
k
P 点到 P’点只有一步；
1 表示（0，0）点到 B 点的路径数。
所以 0 点到 B 点的路径由 0 点到 P 点再从 P 点到 P’点，最后从 P’点到达 B 点。
表示 P’点到 B 点的路径数;
kmmn
−+−
km
−
rn
m
++
=
kn
−
km
−
6
k
M
0
∑
r
+
k
rn
m
1.41 题 分别写出按照字典序，有给定排列计算其对应序号的算法及有给定序号计算其对应排列的算法。
mrmn
−
0
r
+
2
r
+
1
+
m
kn
−
km
−
2
n
−
2
m
−
1
n
−
1
m
−
=∑
+…+
n
m
*1*
r
0
M
0
=
1
+
++
1
2
+
解：利用“字典序法”生成下一排列的算法 ，计算该排列的对应序号，生成已知排列序号算法：
设 int M 为每一排列的对应序号初始时：P1_P2_...Pi-1_Pi_Pi+1_...Pn_ (其中 P1_ =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(n,0)+C(n,1)+ … +C(n,n)]C(m,n)
由 (
y−
2
令 x=y=1 可得 C(n,0) +C(n,1) +C(n,2) +…+C(n,n)= 2n
1.40 题 从 n 个人中选 r 个围成一圆圈，问有多少种不同的方案？
nx +C(n,1)
=C(n,0)
+C(n,2)
1nx
y−
y+
…
nx
)n
x
2
解：圆排列:共有 P(n,r)/r 种不同的方案。
C(m,n)C(m-n,0)=C(m,n)C(n,n)
+…+C(n,n)
ny
左边=2nC(m,n)=右边 命题得证。
7
1.48 题 在由 n 个 0 及 n 个 1 构成的字符串中，在任意前 k 个字符中，0 的个数不少于 1 的个数的字符串有多少？
解 ： 转 化 为 格 路 问 题 ( 弱 领 先 条 件 ), 即 从 (0,0) 到 (n,n), 只 能 从 对 角 线 上 方 走, 可 以 碰 到 对 角 线 , 故 方 案 数 为
C(2n,n)-C(2n,n-1。
1.42 题 (a) 按照 1.41 的要求，写出邻位对换法（排列的生成算法之二）的相应算法.
(b) 写出按照邻位对换法由给定排列生成其下一个排列的算法.
I 为每一排列的对应序号 I=1 （初始化）
解：1：给定排列求相应序号：
设 Int
假定 A[1：n]和 E[2：n]；D[2：n]；B[1：n]都是整数数组，其中 B[1：n]为给定序列
S
：
1
1
[1]
A
←
2
n
i
从 到 作
[ ]
A i
始
q
0
；
A[1
判断 ： 是否与 ： 相等
[ ]
i D i
，
[ ]
i E i
，
B[1
←
←
←
n]
n]
S
：
2
← −
1
终；
D[k] D[k] E[k];
E[k]
若
+
则作
p
←
p D[k];
-1;
←
若相等则输出 值
I
；
S
I
否则
k
n
始
I 1
← +
2
： 从 降到 作
3
←
k
=
否则作
p
始 若
则作
←
1, q
0
=
E[k]
否则作
始
始
p
← +
A[p 1]
p q; r
r;
+ ←
终
终
q 1
← +
终
←
转 终
A[p]; A[p] A[p 1];
S
← +
2
I 为每一排列的对应序号 I=1 （初始化） M 为给定序列号 M=N
2：给定序号求相应排列：
设 Int
假定 A[1：n]和 E[2：n]；D[2：n]；都是整数数组
S
：
1
[1]
1
A
←
2
i
n
从 到 作
[ ]
A i
始
q
；
I
判断 是否与 相等
i 1
从 到 输出 ；
若相等则
[ ]
i D i
，
[ ]
i E i
，
A[i]
← −
←
←
←
M
0
n
1
S
：
2
S
否则
k
： 从n
3
始
；
I 1
I
← +
2
降到 作
D[k]
←
k
p
=
若
否则作
p
始 若
D[k] E[k];
E[k]
+
则作
0
=
E[k]
否则作
始
则作
←
1, q
D[k];
←
p
-1;
←
q 1
← +
终
始
p
← +
A[p 1]
p q; r
r;
+ ←
终
终
←
转 终
A[p]; A[p]
S
2
(a) 由给定排列生成其下一个排列的算法
终；
←
A[p 1];
+
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
