组合数学第四版答案
巡山小妖精
524次浏览
2021年01月26日 14:04
最佳经验
本文由作者推荐
写给女儿的一封信-
组合数学第四版答案
【篇一：组合数学参考答案
(
卢开澄第四版
)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
）也有
4 5
对。
所以这样的序列有
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
个女生的排列是多少？
所以总的排列数为上述
6
种情况之和。
1.3
题
m
个男生，
n
个女生，排成一行，其中
m,n
都是正整数，若
(a)
男生不相邻
(m?n?1); (b) n
个女生形成一个整体；
(c)
男生
a
和女
生
b< br>排在一起；
分别讨论有多少种方案。
解：
(a)
可以考虑插空的方法。
n
个女生先排成一 排，形成
n+1
个空。因为
m?n?1
正好
m
个男生
可以插在
n+1
个空中，形成不相邻的关系。
则男生不相邻的排列个数为
pp
n
n
?
n?1m
(b) n
个女生形 成一个整体有
n
！种可能，把它看作一个整体和
m
个男生排在一起，则排列数 有
(m+1)!
种可能。
因此，共有
n!?(m?1)!
种可能。
(c)
男生< br>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
之间的奇整数的数目，而且没有相同的数字。
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)!! nnn
2n!2n!2
因为(2n-1)!!
是整数所以
(n?1)(n?2)?(2n)
能被
2n
除尽。
1
．
8
题
求
10
和
20
的公因数数目。
4
解：因为
10?2*5?2*5*520?2*5?2*2*5
4030
它们最大公因子为
2*5
转化为求
最大公因子
能除尽的整数个数，能
除尽它的整数是
2a*5b,0??a??40,0??b??30
根据乘法法则，能除尽它的数个数为
41*31=1271
2
1.9
题
试证
n
的正除数的数目是奇数。
2
证明：设有
0?a?n,n?b?n2,
则一定有表达式
n?a?b
，
则
可知符合范围的
a
和
b
必成对出现，所以为偶数。
22
又当
a=b=n
时，表达式
n=a?b
仍然成立。所以
n
的正除数的数目
是
―
偶数
?1‖
为奇数。
1.10
题
证任一正整数
n
可唯一地表成如下形
式
:
证：对
n
用归纳法。
,0≤ai≤i,i
＝
1,2,…
。
40
30
由假设对
n-k!,
命题成立，设
，其中
ak≤k
-1,
，命题成立。
再证表示的唯一性：设
,
不妨设
aj
＞
bj ,
令
j=max{i|ai≠bi}
(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)?n2
k?1
n
n?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?
n
1.13
题
有
n
个不同的整数，从中间取出两组来，要求第
1
组的最小
数大于另一组的最大数。
解题思路：（取法由大到小）
第
1
步：从
n< br>个数由大到小取一个数做为第一组，其它
n-1
个数为
第二组，
组合数为：
c
（
n,1
）
*{c(n-1,1) +c(n-1,2)-
…+c(n
-1,n-1)}
第
2
步：从
n
个数由大到小取两个数做为第一组，其它
n-2
个数为< br>第二组，
组合数为：
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
步：从< br>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< br>个中取
1
个有
c(2,1)
中取法，剩下的每
边
1< br>个取法固定。
所以共有
c(3,1)?c(2,1)?c(2,1)=12
种方案。
1.15
题
求
1
至
1000000
中
0
出现的次数。
解：当第一位为
0
时，后面
6
位组成的数可以从
1-100000
，共
100000
个
0
；
< br>当第二位为
0
时，当第一位取
0-9
时，后面
5
位可 以取
1-9999
，此
外当第一位取
0
时，后面
5
位还可以取为
10000
，这样共有
9999*10+1=99991< br>个
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……
< br>对于第一个分界线，它有
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)
。< br> 1.18
题
8
个盒子排成一列，
5
个有标志的球
放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排
列方案？
5
解：要求空盒不相邻，这样球的位置共有
8
种。而不同标志的 球的
排列有
p5?5!
。所以共有
8*5
！种排列。
8
a)1 111
b) 1 111
在
a)
中
剩下的一个球有四种位置，
b)
中剩下 的一个球也有四种位置，
两者合起来一共有
8
种
1.17
题
n
和
r
都是正整数，而且
r?n
，试证
下列等式：
(a)p?np
rn
n?1r?1
(b)
?1
pp
r
?(n?r?1)p?r!?r(p
?1
?1
(c)
n?1r?1
p
?
nn?r
p
n?1r
,r?n
(d)
p
n?1r
?
p?rp
(e)
n?1
?
p
?l?
p
r
r?1
)
解：
(a) n
(n?1)!n!
pr?1?n?(n?r)!?(n?r)!?
n?1
n
p
等式成立。
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)!?
n
n
p
n?1r
(e)
利用
(d)
的结论可证明本题。
r!?r(p
?1
?
p
n?1r?1
?l?
p
r
r?1
)?
p
?p?rp?rp?rp?l?rp?rp?p?rp?rp?l?rp?rp?p
r
r?1
r?1
r?1
rr
r
r?1r?1
r?2r?1
n?1r?1
n
r?1
r?1r
r?1r?1
r?2r?1
n?1r?1
?1
r
?rp
n
?rp
n?1
?l?rp
r
n?1r
r?1
1.19
题
n+m
位由
m
个
0
，< br>n
个
1
组成的符号串，其中
n≤m+1,
试
问不存在 两个
1
相邻的符号串的数目。
解：
m
个
0进行排列，留出
m+1
个空挡，任选
n
个空挡放
1
，共有
c(m+1,n)
种方案
.
1.21
题
一个盒子里有
7
个无区别的白球，
5
个无区别的黑球，每次
从中随机取走一个球，已知前面取走
6
个，其中< br>3
个是白的，试问
取第
6
个球是白球的概率。
< br>解：
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
个男同< br>志，
10
个女同志，由他们产生一个
7
人的代表团，要求其中甲单位< br>占
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
的路经数
: (a)
路径必须经
过
a
点
; (b)
路径必须过道路
ab; (c)
路径必须过
a
和
c(d)
道路
ab
封锁
(
但
a,b
两点开放
)
解
: (a)
分两步走
o(0,0)→a(3,2) a(3,2)→p(8,5)
，
根据乘法法则
: ?3?2??3?5?
n???2?????3???560
????
3?2??4?3?(b)
分两步走
o(0,0)→a(3,2), b(4,2)→p(8,5)
，根据乘法
法则
:n????????350
?2??3?
????
3?2??3?1??2?2?
(c)
分三步走
: o(0,0)→a(3,2), a(3,2)→c(6,3), c(6,3)→p(8,5),
根据
乘法法则
: n?? ??2?????1?????2???240
??????
（
d
）
ab
封锁路径数加必经
ab
路径数即
o(0,0)→p(8,5)
的
所有路径数有加法法则可得：
?5?8??3?2??4?3?
n??
?5?????2?????3???1287?350?937??????
1.23
题
令
s={1,2,…,n+1},n≥2,t={(x,y, z)|x,y,z
∈
s, xz, yz},
试证
:|t|?
?n?1??n?1?2
k?????2?? k?1?2??3?
n
证明：要确定
x,y,z
的取值，有两种方法，
2
2
2
?k
k?1
n
2
种可能。故
|t|?
?k
k?1
n
2
。
(2)
由
xz, yz
，可以分为三种情况：
①
x=yz,x,y
可看作 一个元素，这种情况等价于从
1,2,…,n+1
中取
2
个进行组合，然后比 较大小，小者为
x(y),
大者为
z,
其组合数为
?
?n?1?
?
；
?2?
n?1?
②
xyz,
等价于从
1,2,…,n+1中取
3
个进行组合，然后比较大小可得
x,y,z,
其组合数为
???
；
?3?n?1?
③
yxz,等价于从
1,2,…,n+1
中取
3
个进行组合，然后比较大小可得x,y,z,
其组合数为
???
。
3??
n?1??n?1??n?1?
所以满足题意的
x,y,z的组合数为
?n?1?+?n?1?+?
＝
???2??
。
???3??3?
??2??3????2??
?n?1??n?1?
由于这两种方法是等价的，故可得
|t|??k2????2??
。证毕。
k?1?2??3?
n
1.24
题
a={(a, b)|a, b
∈
z, 0≤a≤9,0≤b≤5} (a)
求
x-y
平面上以
a
作顶
点的长方形的数目
. (b)
求
x-y
平面上以
a
作顶点的正方形数目
.
解
(b)
：如下图
(b)
，网格左边是
b
的取值，下面是
a
的取值。网格里
是
x-y
平面上对应每个顶点< br>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*1 0=50
。另外十
个点两两相连得直线数目为：
c102=45
又因为
p1p2p3p4p5
共线，所以可算作一条至少
2
点相连的 直线
所
以至少过
15
个点中两点的直线的数目
=50+4 5+1=96
2)
有三种情况
a
：没有
p1p2p 3p4p5
这五个点的三角个数：
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.27
题
6
位男宾，
5
位女宾围一圆桌而坐，（
1
）女宾不相邻有多
少种方案？（
2
）所有女宾在一起有多少种方案？（
3
）一女宾
a
和
两位男宾相邻又有多少种方案？
解
：（
1
）若
5
位女宾不相邻，先考虑
6
位男宾围圆桌而做的方案
数，然后女宾插入
q
（
6
，
6
）
*6*5*4*3*2=86400
（
2
）把
5
位女宾看
成一个整体，然后插入
q
（
6
，
6< br>）
*6*p(5,5)=86400
（
3
）
c
（5
，
1
）
*c
（
6
，
2
）< br>*q
（
8
，
8
）
=194000
c(5,1)*c(6,2)*c(5,2)*p(4,2)*7
！
1.28
题
k
和
n
都是正整数，
kn
位来宾围 着
k
张圆桌而坐，试求其
方案数。
解：若每个圆桌的的 人数相等，则每个桌子有
n
个人。因为圆周排
列的个数为因此本题的结果为
p
r
(kn)!(kn)!
?k
。
n?n?nn
1.29
题
从
n
个对象中取个
r
做圆排列，求其方案数目。
1=r=n
解：
c(n,r)*q< br>（
r,r
）
=c(n,r)*(r-1)!
1.31
题试证任意
r
个相邻数的连乘：
(n?1)(n?2)?(n?r)
被
r
！除尽
.
【篇二：组合数学
+
卢开澄版
++
答案第四章】
x
是群
g
的一个元素，存在一最小的正整数
m
，使
xm=e
，则称
m
为
x
m
n
m?n
m
,
等式右边
x x
＝
x
nmm?n
，
?ab?ba
，即所有
的阶，试证：
c=
｛
e,x,x2, …,xm
-1
｝
证：
x
是
g
的元素，
g
满足封闭性所 以，
xk
是
g
中的元素
c
∈
g
再证
c
是群：
xa
∈
c, (xa)-1= xb=xm-a
4.3
设
g
是阶为
n
的有限群，则
g
的所有元素的阶都不超过
n.
证明：设
g
是阶为
n
的有限群，
a
是
g
中的任意元素，
a
的阶素为
k
，
则此题要证
k?n
首先考察下列
n+1
个元素
a,a,a,a,..a..
234n?1
由群的运算的 封闭性可知，这
n+1
个元素都属于
g,
，而
g
中仅有n
个元素，所
以由鸽巢原理可知，这
n+1
个元 素中至少有两个元素是相同的，不
妨设为
a
i
i
?
a
i
i?j
（
1?j?n
）
j
a
?
a?a
j
j
由群的性质
3
可知，
a
是单位元 ，即
a=e
，又由元素的阶数的定义
可知，当
a
为
k
阶元素时
a=e
，且
k
是满足上诉等式的最小正整数，
由此可证< br>k?j?n
k
4.4
若
g
是阶为< br>n
的循环群，求群
g
的母元素的数目，即
g
的元素
可 表示
a
的幂：
a,a2……..an
所以群
g
中母元素的数目为
n(1-
1/p1)………(1
-1 /pk)
个
. 4.5
证明循环群的子群也是循环群
证明：设
h
是
g=a
的子群，若
h=e,
显然
h
是循环群，否则取
h
中
最小的正方幂元
am
，下面证明
am
是
h
的生成元
,
易见
am?h< br>，只要
证明
h
中的任何元素都可以表成
am
的整数次方，由除 法可知存在
q