tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 数学 >>

组合数学第一章答案


组合数学第 1 章答案

1 2, 50 1.1 从 { , ? ? ?, }中找两个数 {a, b},使其满足 1
(1) | a ? b |= 5 ; ) (2) | a ? b |≤ 5 )
或 a ?b = 5 a ? b = ?5 则有 45种 45种 共有 90 种。

解: (1)根据 | a ? b |=

5 可得

(2)根据 | a ? b |≤ 5



b?5 ≤ a ≤ b+5 { a, 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!

个男生,n 个女生,排成一行, 都是正整数, 1.3 m 个男生,n 个女生,排成一行,其中 m,n 都是正整数,若 男生不相邻( n+1) (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) = (2n)! 2n(2n ? 1)! (2n ? 1)! = =2 n! n(n ? 1)! (n ? 1)! (2n ? 2)(2n ? 1)(2n ? 3)! (2n ? 1)(2n ? 3)! =2 = 22 = ... (n ? 1)(n ? 2)! (n ? 2)! = 2 n (2n ? 1)(2n ? 3)...3

(n+1)(n+2)…(2n)被 2 k 除尽。

所以(n+1)(n+2)…(2n)能被 2 k 除尽。

求 1040 和 2030 的共因数的数目. 解: 10 40=2 40 * 5 40 20 30=260 * 5 30 40 30 ∴ 10 和 20 的公因子有 40*30=1200 个 1.9 试证 n 的平方的正除数的数目是奇数 答案:因为 n 的平方一定是两个数的乘积,一定是两个不同的数的乘积或唯一的 一个相同的 数的乘积。例如,16 可以是 1*16,2*8 或 4*4,前面的都是成 对出现的,只有 4 是一个 数,所以他们的和一定是奇数。 1.10 证明任一正整数 n 可唯一地表示成如下形式: 1.8 n= ∑ ai ? i ! ,
i ≥1

0 ≤ ai ≤ i ,

i ≥1

证明:对 n 用数学归纳法 数学归纳法 ① 当 n=0,1 时,0=0 ? 1! , 1=1 ? 1!。命题成立。 ② 假设对于小于 n 的非负整数,命题成立。 ③ 对 于 n , 设
k ! ≤ n < ( k + 1)!





0 ≤ n ? k ! < ( k + 1)!? k ! = ( k + 1 ? 1) ? k ! = k ? k !

由②,对 n ? k ! 命题成立。设 n ? k ! = ∑ ai ? i ! ,其中 0 ≤ ai ≤ i ,
i =1

k

0 ≤ ak ≤ k ? 1
k

( 原 因 是 0 ≤ n ? k!< k ?k! 而 不 能 等 于 k ?k! ) , 那 么
k ?1 i =1

n = ∑ ai ? i ! + k ! = ∑ ai ? i ! + ( ak + 1) ? k ! ,其中 0 ≤ ak + 1 ≤ k ,命题成立。
i =1

再证唯一性: 再证唯一性 设 n = ∑ ai ? i ! = ∑ bi ? i ! , 不 妨 设 a j > b j , j = min{i | ai ≠ bi } , 即
i =1 i =1 k k

a1 ?1!+ a2 ? 2!+ a3 ? 3!+ L = b1 ?1!+ b2 ? 2!+ b3 ? 3!+ L ,

假设 a1 = b1 , a2 = b2 , a3 ≠ b3 ,则 j=3。那么,因为 ai 与 bi 前 j 项相等, 上式两边均减去前 j 项,即 ∑ ai i ! = ∑ bi i ! ,即
i≥ j i≥ j

a j j !+ a j +1 ( j + 1)!+ a j + 2 ( j + 2)!L = b j j !+ b j +1 ( j + 1)!+ b j + 2 ( j + 2)!L

将上式两边都除以 ( j + 1)! ,得

a j j! ( j + 1)!

+ a j +1 + a j + 2 ( j + 2)L =

bj j ! ( j + 1)!

+ b j +1 + b j + 2 ( j + 2)L

可以看出,上式的余数为 a j j ! = b j j ! 与假设矛盾。因此 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) =左边 所以等式成立。 1—12 证明: 试证:

∑ kC (n, k ) = n2
k =1

n

n ?1

(1+x) n =C(n,0)+C(n,1)x+C(n,2)x 2 +…+C(n,n)x n

两边求导,并令 x=1 代入
n(1+1) n ?1 =C(n,1)+C(n,2)x+C(n,3)x 2 +… +C(n,n)x n ?1 n2 n ?1 = ∑ kC ( n, k )
k =1 n

组合意义: 设有 n 个不同的小球,A,B 两个盒子,A 盒中恰好放 1 个球,B 盒中可放任意 个球.有两种方法放球: 第一种: 先从 n 个球中取 k 个球(k≥1),在从 k 中挑一个放入 A 盒,方案数共 为 ∑ kC (n, k ) ,其余放入 B 盒.
k =1 n

第二种: 先从 n 个球中任取一球放入 A 盒,剩下 n-1 个球每个球有两种可能,要么 放入 B 盒,要么不放,故方案数为 n2 n ?1 , 显然相等. 1.13:有 N 个不同的整数,从中取出两组来,要求第一组的最小数大于第二组的 : 个不同的整数,从中取出两组来, 最大数。 最大数。 解:本题求取两组数的取法。 我们首先从 N 中去 M 个数(2<=M<=N),因为 M 个数是不同的,所以存在一个 递增的序列 A=a1,a2,a3,a4……aM (a1<a2<a3<a4……<aM)。 然后我们从序列A中按 顺序取出{a1}{a1,a2}{a1,a2,a3}..{a1,a2,a3,a4……aM-1}作为第一组,剩 , , ... 下的作为第二组。就可以保证第一组的最小数大于第二组的最大数。从 N 中去 M,共有 C(n,m)种,每一种 M 对应一个序列 A,每一个序列 A 对应 M-1 种 分组方法。所以对于每一个 M 共有,C(n,m)×(m-1)种分组方法。又因为 2<=M<=N,所以总共的分组方法为:

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 1) 2) 3) 4) 5) n 和 r 都是正整数,而且 r ≤ n,试证下列等式 都是正整数, ,
? prn = nprn?11

prn = ( n ? r + 1) prn?1

prn =

n prn ?1 , r < n n?r

prn +1 = prn + rprn?1
? prn +1 = r !+ r ( prn?1 + prn?11 + …… + prr?1 )

1) 证明:左边=n*(n-1)……(n-r+1) 右边= n*(n-1)……(n-r+1) 所以 左边=右边 同理: (2) (3) (4)得证。 5 ) 证 明 : 利 用 ( 4 ) ,
prn +1 = prn + rprn?1

? ? = ( prn ?1 + rprn?11 ) + rprn?1 = prn ?1 + r ( prn?11 + prn?1 ) = ……=等式右边

1.18

8 个盒子排成一列,5 个有标志的球放到盒子中,每个盒子最多放一个球,要 求空盒子不相邻,问有多少种排列方案。 解: P( 5 , 5 )*C( 6 , 3)=2400(种) 答:共有 2400 种方案。

1.19.n + m 位由 m 个 0,n 个 1 组成的符号串,其中 n ≤ m+1,试问不存在两个 1 相邻的符号串的数目。 解:该题可以看作是往 m 个 0 里插入 n 个 1,即从 m+1 个空中选取 n 个空 放 1,这样就使得不存在两个 1 相邻,总的解决方案数为: C ( m + 1, n) 1.20 甲单位有 10 个男同志, 个女同志, 4 乙单位有 15 个男同志, 个女同志, 10 由他们产生一个 7 人的代表团,要求其中甲单位占 4 人,而且 7 人中男同 志 5 位,试问有多少种方案? 解: 根据题意,符合要求的组合法有 3 种: (1)甲单位 4 男 0 女,乙单位 1 男 2 女; (2)甲单位 3 男 1 女,乙单位 2 男 1 女; (3)甲单位 2 男 2
4 0 1 2 女,乙单位 3 男 0 女。则对应的组合数为: (1) C10 C 4 C15 C10 = 141750 , 3 1 2 1 (2) C10 C 4 C15 C10 = 504000 , 2 3 0 (3) C10 C 42 C15 C10 = 122850 。

因此,符合条件的方案数共有:141750+504000+122850=768600 种。 1.21 一个盒子里有 7 个无区别的白球,5 个无区别的黑球。每次从中随机取走 一球,已知前面取走 6 个,其中 3 个是白的。试问第 6 个球是白球的概率? 解:设 6 个球的编号分别为 1、2……6。6 个球中第 6 个球是白球的所有可能方 案为:126、136、146、156、236、246、256、346、356、456,既有 10 种可能。 那么第 6 个球是白球的概率为 10/C(6,3)=1/2。

1.22 求图 1-22 中从 0 到 P 的路径数。 的路径数。 (1)路径必须经过 A 点 (2)路径必须过道路 AB

(3)路径必须过 A 点和 C 点 (4)道路 AB 封锁(但 A,B 两点开放)
3 5 解题: (1) C3+ 2 × C5+ 3 = 560 3 (2) C3+ 2 × C44+3 = 350 1 (3) C33+ 2 × C3+1 × C22+ 2 = 240 3 (4) C55+8 ? C3+ 2 × C44+3 = 937

1.23 令 s = {1, 2,......., n + 1}, n ≥ 2, T = {( x, y , z ) | x, y , z ∈ s, x < z , y < z} ,试证: 试证:
n ? n + 1? ? n + 1? T = ∑k2 = ? ? + 3? ? k =1 ? 2 ? ? 3 ?

解题: (1) :因为 x,y 的最小值为 1,所以 z ∈ (2,3, 4,........n) 当 z=2 时:x=y=1,
1 1 当 z=3 时:x,y 各有两种选择 C2C2

………
1 1 当 z=n+1 时:x,y 各有两种选择 Cn Cn

即: T = ∑ k 2
k =1

n

(2) :因为 x, y , z ∈ s 且 x < z , y < z 。当 x=y 时,从 (1, 2,......n + 1) 取两 个数,大的给 z,小的给 x,y,有 Cn2+1 。当 x ≠ y 时,(1, 2,......n + 1) 取三个数,
n ? n + 1? ? n + 1? 3 大的给 z,小的给 x 或 y,有 2Cn +1 ,即: T = ∑ k 2 = ? ? + 3? ? k =1 ? 2 ? ? 3 ?

1.24 A={(a,b)|a,b ≤ Z,0 ≤ a ≤ 9,0 ≤ b ≤ 5} (1) 求 x-y 平面上以 A 作顶点的长方行数目; (2) 求 x-y 平面上以 A 作顶点的正方形数目; 如图所示

5 4 3 2 1

0

1

2

3

4

5

6

7

8

9

解:思想是分别以纵坐标 0、1、2、3、4 为起点,横坐标和纵坐标一起够成的长 方形 即:4*C(9,1)+4*C(9,2)+4*C(9,3)+4*C(9,4)+4*C(9,5)+5*C (9,6)+5*C(9,7)+5*C(9,8)+5 + 3*C(9,1)+3*C(9,2)+3*C (9,3)+3*C(9,4)+4*C(9,5)+4*C(9,6)+4*C(9,7)+4*C(9,8) +4 + 2*C(9,1)+2*C(9,2)+2*C(9,3)+3*C(9,4)+3*C(9,5) +3*C(9,6)+3*C(9,7)+3*C(9,8)+3 + C(9,1)+C(9,2)+C(9,3)+C(9,4)+C(9,5)+C(9,6)+C (9,7)+C(9,8)+1=13374 即以 A 作顶点的长方形数目为 13374 个。 同理以 A 作顶点的正方形数目为: C(9,1)+C(9,2)+C(9,3)+C(9,4)+C(9,5)+ C(9,1)+C(9,2)+C(9,3)+C(9,4)+ C(9,1)+C(9,2)+C(9,3)+ C(9,1)+C(9,2)+ C(9,1)=1071 即以 A 作顶点的正方形数目为 1071 个。

1.25 平面上有 15 个点,P1,P2,…,P15,其中 P1,P2,P3,P4,P5 共线,此外 不存在 3 点共线的。 (a)求至少过 15 个点中两点的直线的数目; (b)求由 15 个点中 3 点组成的三角形的数目。 解: (a)根据题意,符合条件的直线有三种可能: (1)P1,P2,P3,P4,P5 构 成的直线, 1 条; 有 (2) 6~P15 中的任选两点构成的直线, C10 = 45 P 有 2 条; (3)由 P1~P5 中的一个点及 P6~P15 中的一个点构成的直线,有
1 1 C 5 C10 = 50 条。因此,符合要求的直线共有 1+45+50=96 条。

(b)根据题意,符合条件的三角形有三种可能: (1)P1~P5 中任选两个点
1 及 P6~P15 中任选一个点构成三角形:有 C 52 C10 = 100 个; (2)P1~P5 中

有 1 2 ( 任选一个点及 P6~P15 中任选两个点构成三角形: C 5 C10 = 225 个; 3)

3 P6~P15 中任选三个点构成三角形:有 C10 = 120 个。因此,共可组成三

角形 100+225+120=445 个。 1.26. S = {1, 2,...,1000}, a, b ∈ S , 使ab ≡ 0mod5,求数偶{a,b}的数目。 解:由题知 ab ≡ 0 mod 5 ,说明 a*b 能被 5 整除。则分为两种情况: ① a ,b 同时为 5 的倍数 1000 中 5 的倍数有 200 个 方案数为:200*199/2 ② a ,b 不同时为 5 的倍数,即 a ,b 中有一个不是 5 的倍数 方案数为:800*200 总的 总的方案数为:200*199/2+800*200 1.27 6 位男宾,5 位女宾围一圆桌而坐, (1) 女宾不相邻有多少种方案。 (2) 所有女宾在一起有多少种方案。 (3) 一女宾 A 和两位男宾相邻又有多少种方案。 解: (1)5!*P( 6 , 5 )=120*720 =86400 答:女宾不相邻有 86400 种方案。 (2)6!*5!=86400 答:所有女宾在一起有 86400 种方案 (3)8!*2*C(6 ,2)=40320*2*3*5=1209600 答:一女宾 A 和两位男宾相邻又有 1209600 种方案。 1.28 k 和 n 都是正整数,kn 位来宾围着 k 张圆桌而坐,试求方案数。 都是正整数, 张圆桌而坐,试求方案数。 解; 方案数为: [C(nk,n)*(n-1)!]*[ C(n(k-1),n)*(n-1)!] *[ C(n(k-2),n)*(n-1)!]*……*[ C(n,n)*(n-1)!] 整理得:(n-1)!k * C(nk,n)* C(n(k-1),n)*……*C(n,n)= (n-1)!k *(nk)!/ (n!) k=(nk)!/ n k 1.29 个作圆周排列,求其方案数? 从 n 个对象中取 r 个作圆周排列,求其方案数?

解: C (n, r ) × (r ? 1) ! 1.30 试证下列等式
? n ? n ? n ? 1? (1) ? ? = ? ?, 1 ≤ r ≤ n ? r ? r ? r ?1 ? ? n ? n ? r +1? n ? (2) ? ? = ? ?, 1≤ r ≤ n r ?r ? ? r ? 1? ?n? n ? n ? 1? (3) ? ? = ? ?, 1≤ r ≤ n ?r ? n?r ? r ?

证明: (1)
n! r !(n ? r )! n (n ? 1)! n! 右边 = ? = r (r ? 1)!(n ? r )! r !(n ? r )! 左边 = ? n ? n ? n ? 1? 所以 ? ? = ? ?, 1≤ r ≤ n ? r ? r ? r ?1 ? (2) n! 左边 = r !(n ? r )! n ? r +1 n! n! 右边 = ? = r (r ? 1)!(n ? r + 1)! r !(n ? r )! ? n ? n ? r +1 ? n ? 所以 ? ? = ? ?, 1≤ r ≤ n r ?r ? ? r ? 1? (3) n! 左边 = r !(n ? r )! n (n ? 1)! n! 右边 = ? = n ? r r !(n ? 1 ? r )! r !(n ? r )! ?n? n ? n ? 1? 所以 ? ? = ? ?, 1 ≤ r ≤ n ?r ? n?r ? r ? 1.31 试证明任意 r 个相临数的连乘:
(n + 1)( n + 2)...( n + r )

被 r!除尽

?n+ r? 解: 显而易见, ? ? 是一个整数,由 ?r ? ?n+ r? (n + r )! (n + r )! (n + 1)(n + 2)...(n + r ) = = ? ?= r !n ! r! ?r ? r !( n + r ? r ) ! ?n+ r? ( n + 1)( n + 2)...( n + r ) 由于 ? 是整数,那么 ? 是整数,所以 r! ?r ?
(n + 1)( n + 2)...( n + r ) 可以被 r!除尽

1.32: 在 a,b,c,d,e,f,x,x,x,y,y 的排列中,要求 y 必须夹在两个 X 之间,问这样 的排列中, 之间,

的排列数等于多少? 的排列数等于多少? 解:要求 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= p1 p2 p3 .............. ,其中
a1 a2 a3

p1 , p2 ....... 是质数,a1, a 2.... 是正整数。

则 n 的因子数有(a1+1)(a2+1)(a3+1)…………个。 得
n 2 = p1
2 a1

p2

2a 2

p3

2a 3

.............. ,因为(2a1+1),(2a2+1),(2a3+1)………..

都是奇数, 所以
n 2 的因子数为(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 ?? 0 ? ? m ? 1 ?? 1 ? ? m ? 2 ?? 2 ? ? 0 ?? m ? ? m ?

的组合意义.
y

解 : B(m-n,m)

A(-1,m)

m

. . .

. . .

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

-1

0

m-n

可看作是格路问题:左边第 i 项为从点 C 到点(-1,i)直接经过(0,i)的路径, 再到点 B 的所有路径。左边所有项的和就是从 C 点到 B 点的所有路径数 即为右边的意义. ? r ? ? r + 1? ? r + 2 ? ? n ? ? n + 1? ? + ... + ? ? = ? 1.38 给出 ? ? + ? ?r? ?r ? + ?r ? ? ? ? r ? ? r + 1 ? 的组合意义。 ? ? ? ? ? ? ? ? ? ? ? 解:设 A = {a1 , a 2 ,..., a n ?r +1 , a n +1 },从 A 中取 r+1 个元素组合成 C,考虑以下 n-r+1 种情况: ?n? (1) a1 ∈ C ,则 A 需从 A \ {a1 } 中取 r 个与 a1 配合,构成 C,共 ? ? 中可能。 ?r ? ? ? ? n ? 1? (2) a1 ? C , a 2 ∈ C ,则需从 A \ {a1 , a 2 }中取 r 个,加上 a 2 构成 C,共 ? ? r ? 种可 ? ? ? 能。 (n-r) a1 , a 2 ,..., a n ?r ?1, ? C ,则需从 A \ {a1 , a 2 ,..., a n ? r }中取 r 个组合,再加上 a1 构成 ? r + 1? C,共 ? ? r ? 种可能。 ? ? ? ?r? (n-r+1) a1 , a 2 ,..., a n ? r ?1, a n ? r ? C ,这时只有 ? ? =1 种可能。 ?r? ? ?

? r ? ? r + 1? ? r + 2 ? ? n ? ? n + 1? ? + ... + ? ? = ? 故? ? + ? ?r? ?r ? + ?r ? ? ? ? r ? ? r + 1? ? ? ? ? ? ? ? ? ? ? ? 1.39

证明: 证:组合意义,右边:m 个球,从中取 n 个,放入两个盒子,n 个球中每个球都有两种 放法,得到可能的方案数。 左边: i 项的意义是一个盒子中放 i 个,另一个盒子放 第 n-i 个,所有的方案数相加应该等于右边。
左式=∑ C (m, k )C (m ? k , n ? k )
k =0 n

=∑ =∑ =∑ =∑
n n n

m! (m ? k )! ? k = 0 k!( m ? k )! ( m ? n )!( n ? k )!
n

m! n! ? k = 0 k! n! ( m ? n)!( n ? k )! m! n! ? k = 0 ( m ? n)! n! k!( n ? k )! n! ? C (m, n) k = 0 k!( n ? k )!

= 2 n C (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,若 S3. i = max{ j | S4. h = max{k |

p p ... p
1 2

<-12…N,LEN=1;
n

p
<

j ?1

>

p
}; };

,则退出;
j

p

j ?1

p

j

p

i ?1

<

p

k

S5.将

P

i?1



p

h
'

互换的
1

p p ... p
1 2 ' n

'

1

' n



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

p p ... p
1 2

,LEN++;
1 ' '

p和p
i

'

' n

互换,得

p p ... p ... p ;
1 2 n i ' ' n i

'

S8.A[LEN]<-

p p ... p ... p , LEN++,转到 S2;
1 2

'

1

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

p p ... p
1 2 1


n

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

p p ... p
2

,则输出 j,退出;
n

否则 j++; 由给定序号计算其对应的算法 S1.输入序号 j; S2.输出 A[j][],退出;

1.42( 的要求,写出邻位对换法(排列的生成算法之二) 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)<C(n,k-1) 当 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)证明

( 2n)! (3n) ! 都是整数。 和 n n 都是整数。 n 2 2 ?3

( n 2 )! 是整数。 是整数。 (n!)n+1

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

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

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

(3n)! (3n)! (3n)! = = n n ,得证。 n n (3!) (3 × 2) 3 ?2

(2)设有 n 2 个不同的球,将他们放入 n 个相同的盒子,每盒 n 个球,这个 方案数应该是整数。由(1)可知,将 n 2 个不同的球放入 n 个不同盒子的方案数 为

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

( 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) = 2 n (2)相当于从 2n+1 个不同的小球中分别取出个小球( 0 ≤ m ≤ n ) ,再从 n 个不同小球中取出 n-m 个小球。则共有方案数: ∑ C (2n + 1, m)
m =0 n

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

出现 0 次,而当 n=1 时, 3n +1/2=2,是正确的。 假设当 n=k 时是正确的,即 0 出现 3k +1/2 次,计算 0 出现 奇数次的方案, 因为总方案数为 3k , 0 出现奇数次的方案为 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,有 2 n 种可能,所以方案为 ( 0 ) × 2 n ,最后一项为

当 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)。 所以总的方案数为 ∑ C (m,2n)C (2n, n)3( m ? 2 n ) .
x =0 m/2

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, 个 1 组成的字符串中,出现 01 或 10 的总次数为 k 的, n 有多少个? 解:(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”插入头或尾,总方案数为 k ?1 k +1 2C ( m ? 1, )C ( n ? 1, n ? ) 2 2 k k k ?2 k+2 若 k 为偶数,总方案数为 C ( m ? 1, )C ( n ? 1, n ? ) + C ( m ? 1, )C ( n ? 1, n ? ) 2 2 2 2 第一问,出现 4 个 01 或 10,说明 5 个 0 被分成了 3 段,四个 1 被分成了两段, 或者 5 个 0 被分成了 2 段, 四个 1 被分成了 3 段, 然后夹在一起形如 001101100; 然后夹在一起形如 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? ?18 ? ? =? ? =? ?种 解: ? ?r ? ?3 ? ?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 个女人先沿圆桌坐下,这时正好有 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-1)!。 r) 剩下 (n-r) 个人再进行圆排列 (n-r-1)。 ! 根据乘法原理一共有 C (n, × r) (r-1) !× (n-r-1)。 ! 1.58 一圆周上 n 个点标以 1,2,…,n.每个点与其他 n-1 个点连以直线,试问 这些直线交于圆内多少点? 解:
x1 xn
x1 xn

xi

图a

图b

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

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

条边,也就有这么多个交点

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

∑ ?1

?i ? 2? ? n ? i ? ??? ? i =3 ? ? ?1 ?

与点 1 相连的直线上的交点个数都求出来了,就可以先把点 1 去掉,如图 b, 计算剩下的 n-1 个点的直线的交点个数。 所以 n 个点一共是: ?i ? 2? ? m ? i ? ??? ? m = 4 i =3 ? ? ?1 ?

∑ ∑ ?1

n

m ?1

?i ? 2? ? m ? i ? 那么这些直线交于圆内 ∑ ∑ ? ??? ? 个交点 m = 4 i =3 ?1 ? ?1 ?
n m ?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


推荐相关:

组合数学课后习题答案

组合数学课后习题答案_工学_高等教育_教育专区。《组合数学》(第四版)清华大学出版社 第一章答案 1.(a) 45 ( {1,6},{2,7},{3,8},…,{45,50} ) ...


组合数学第四版卢开澄标准答案-第一章

组合数学第四版卢开澄标准答案-第一章_理学_高等教育_教育专区。官方标准答案第1 章 排列与组合 1.1 从{1,2,…,50}中找一双数{a,b},使其满足: [解] ...


组合数学第一章答案

组合数学第一章答案_工学_高等教育_教育专区。组合数学前三章课后习题答案宗传玉) 1.1 题(宗传玉) 从{1,2,……50}中找两个数{a,b},使其满足 (1)|a...


组合数学习题解答

组合数学习题解答_数学_自然科学_专业资料。组合数学 组合数学 ★★★第一章:★★★ 1、用六种方法求 839647521 之后的第 999 个排列。提示:先把 999 换算成...


组合数学答案

组合数学第3章答案 24页 10财富值 应用组合数学(答案) 44页 2财富值喜欢此文档的还喜欢 组合数学参考答案(卢开澄第... 60页 2财富值 组合数学第一讲 59页 ...


组合数学课后答案

作业习题答案 习题二 2.1 证明:在一个至少有 2 人的小组中,总存在两个人,他们在组内所认识的人数相同。 证明: 人的小组中,总存在两个人,他们在组内所...


组合数学答案

组合数学课后答案 15页 2财富值 组合数学第3章答案 24页 10财富值喜欢此文档的还喜欢 组合数学答案 57页 2财富值 组合数学习题答案卢开澄 60页 5财富值 数字图...


李凡长版 组合数学课后习题答案 习题1

李凡长版 组合数学课后习题答案 习题1_法学_高等教育_教育专区。李凡长版 组合数学课后习题答案习题1第一章 排列组合 1、 在小于 2000 的数中,有多少个正整数含有...


组合数学1章课后习题答案

组合数学1章课后习题答案_理学_高等教育_教育专区。清华大学出版社第四版 ---卢开澄、卢华明 编著宗传玉) 1.1 题(宗传玉) 从{1,2,……50}中找两个数{a,...


组合数学课后答案

组合数学课后答案_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 组合数学课后答案_理学_高等教育_教育专区。 今日推荐 ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com