没有合适的资源?快使用搜索试试~ 我知道了~
组合数学参考答案(卢开澄第四版)60页
4星 · 超过85%的资源 需积分: 11 48 下载量 31 浏览量
2012-10-22
12:42:49
上传
评论
收藏 3.95MB DOC 举报
温馨提示
试读
63页
组合数学参考答案(卢开澄第四版)60页,答案包括一到7章的课后习题答案,很详细
资源推荐
资源详情
资源评论
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)男生不相邻 ; (b)n 个女生形成一个整体; (c)男生 A 和女生 B 排在一起;
分别讨论有多少种方案。
解:(a) 可以考虑插空的方法。
n 个女生先排成一排,形成 n+1 个空。因为 正好 m 个男生可以插在 n+1 个空中,形成不相邻的关系。
则男生不相邻的排列个数为
(b) n 个女生形成一个整体有 n!种可能,把它看作一个整体和 m 个男生排在一起,则排列数有(m+1)!种可能。
因此,共有 种可能。
(c)男生 A 和女生 B 排在一起,因为男生和女生可以交换位置,因此有 2!种可能,
A、B 组合在一起和剩下的学生组成排列有(m+n-1)!
(这里实际上是 m+n-2 个学生和 AB 的组合形成的)种可能。共有组合数为
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 题 试证: 被 2
n
除尽。
1
证明:因
因为(2n-1)!!是整数所以 能被 2
n
除尽。
1.8 题 求 和 的公因数数目。
解:因为
它们最大公因子为 转化为求 最大公因子 能除尽的整数个数,能除尽它的整数是
根据乘法法则,能除尽它的数个数为 41*31=1271
1.9 题 试证 的正除数的数目是奇数。
证明:设有 , 则一定有表达式 ,
则 可知符合范围的 和 必成对出现,所以为偶数。
又当 a=b=n 时,表达式 =a b 仍然成立。 所以 的正除数的数目是“偶数 ”为奇数。
1.10 题 证任一正整数 n 可唯一地表成如下形式: ,0≤a
i
≤i,i=1,2,…。
证:对 n 用归纳法。
先证可表示性:当 n=0,1 时,命题成立。
假设对小于 n 的非负整数,命题成立。
对于 n,设 k!≤n<(k+1)!,即 0≤n-k!<k·k!
由假设对 n-k!,命题成立,设 ,其中 a
k
≤k-1, ,命题成立。
再证表示的唯一性:设 , 不妨设 a
j
>b
j
,令 j=max{i|a
i
≠b
i
}
a
j
·j!+a
j-1
·(j-1)!+…+a
1
·1! =b
j
·j!+b
j-1
·(j-1)!+…+b
1
·1!,
矛盾,命题成立。
1.11 题 证明 nC(n-1,r)= (r+1)C(n,r+1),并给予组合解释.
证:
所以左边等于右边
组合意义:等式左边:n 个不同的球,先任取出 1 个,再从余下的 n-1 个中取 r 个;
等式右边:n 个不同球中任意取出 r+1 个,并指定其中任意一个为第一个。
所以两种方案数相同。
1.12 题 证明等式:
证明:
1.13 题 有 N 个不同的整数,从中间取出两组来,要求第 1 组的最小数大于另一组的最大数。
2
解题思路:(取法由大到小)
第 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}
总的组合数为:
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*5!种排列。
8 种排列如下两类。因为要求空盒不相邻,途中 1 代表球
a) 1 1 1 1
b) 1 1 1 1
在 a)中 剩下的一个球有四种位置,b)中剩下的一个球也有四种位置,两者合起来一共有 8 种
1.17 题 和 都是正整数,而且 ,试证下列等式:
解:(a) 等式成立。
3
(b) 等式成立。
(c) 等式成立。
(d)
(e)利用(d)的结论可证明本题。
1.19 题 n+m 位由 m 个 0,n 个 1 组成的符号串,其中 n≤m+1,试问不存在两个 1 相邻的符号串的数目。
解:m 个 0 进行排列,留出 m+1 个空挡,任选 n 个空挡放 1,共有 C(m+1,n)种方案.
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 的路经数:
(a) 路径必须经过 A 点; (b) 路径必须过道路 AB;
(c) 路径必须过 A 和 C (d) 道路 AB 封锁(但 A,B 两点开放)
解: (a)分两步走 O(0,0)→A(3,2) A(3,2)→P(8,5),根据乘法法则:
(b)分两步走 O(0,0)→A(3,2), B(4,2)→P(8,5),根据乘法法则:
(c)分三步走: O(0,0)→A(3,2), A(3,2)→C(6,3), C(6,3)→P(8,5), 根据乘法法则:
(d)AB 封锁路径数加必经 AB 路径数即 O(0,0)→P(8,5)的所有路径数有加法法则可得:
1.23 题 令 s={1,2,…,n+1},n≥2,T={(x,y,z)|x,y,z∈s, x<z, y<z}, 试证):
证明:要确定 x,y,z 的取值,有两种方法,
(1)可先确定 z,由题意可得 当 z=2 时,x 可取 1,y 可取 1,根据乘法法则,x,y 取值共有 1×1=1
2
种可能;
当 z=3 时,x 可取 1,2,y 可取 1,2,根据乘法法则,x,y 取值共有 2×2=2
2
种可能;
当 z=4 时,x 可取 1,2,3,y 可取 1,2,3,根据乘法法则,x,y 取值共有 3×3=3
2
种可能;
……
P
C
A B
4
当 z=n+1 时,x 可取 1,2,…,n,y 可取 1,2,…,n,根据乘法法则,x,y 取值共有 n×n=n
2
种可能。
根据加法法则,当 z 取 2,3,…,n+1 时,x,y 取值共有 种可能。故 。
(2)由 x<z, y<z,可以分为三种情况:
①x=y<z,x,y 可看作一个元素,这种情况等价于从 1,2,…,n+1 中取 2 个进行组合,然后比较大小,小者为 x(y),大者
为 z,其组合数为 ;
②x<y<z,等价于从 1,2,…,n+1 中取 3 个进行组合,然后比较大小可得 x,y,z,其组合数为 ;
③y<x<z,等价于从 1,2,…,n+1 中取 3 个进行组合,然后比较大小可得 x,y,z,其组合数为 。
所以满足题意的 x,y,z 的组合数为 + + = 。
由于这两种方法是等价的,故可得 。证毕。
1.24 题 A={(a , b)|a, b∈Z, 0≤a≤9,0≤b≤5} (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 个点 P
1
,P
2
。。。P
15
,其中 P
1
P
2
P
3
P
4
P
5
共线,此外不存在 3 点共线的。
(1)求至少过 15 个点中两点的直线的数目 (2)求由 15 个点中 3 点组成的三角形的数目
解:1)由题意知:P
1
P
2
P
3
P
4
P
5
共线,此外不存在 3 点共线的,所以与这五点分别相连的其他的十点的直线数目为:
5*10=50。另外十个点两两相连得直线数目为:C
10
2
=45
又因为 P
1
P
2
P
3
P
4
P
5
共线,所以可算作一条至少 2 点相连的直线
所以至少过 15 个点中两点的直线的数目=50+45+1=96
2)有三种情况 a:没有 P
1
P
2
P
3
P
4
P
5
这五个点的三角个数:C
10
3
=120
b:有这五个点的其中一个点:5*C
10
2
225 c:有着五个点的两个点:10*C
5
2
=100
5
剩余62页未读,继续阅读
美杜莎_Ly
- 粉丝: 0
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
前往页