当前位置：文档之家 › 应用组合数学第二章答案

应用组合数学第二章答案

  • 格式：pdf
  • 大小：247.66 KB
  • 文档页数：15

下载文档原格式

  / 15

合集下载

组合数学第2章答案

组合数学第2章答案

组合数学第2章答案2.1 求序列{0，1，8，27，…3n …}的母函数。

解：()()++++++=++++++=nn n x n x x x x G x a x a x a x a a x G 3323322102780()46414321313=+-+--==-----n n n n n n n a a a a a n a n a左右同乘再连加：464:0464:0464:0464:4321543211123455012344=+-+-=+-+-=+-+-=+-+-----------n n n n n n n n n n n n a a a a a x a a a a a x a a a a a x a a a a a x母函数：()()42162036-+-=x x x x G2.2 已知序列()()3433{,,……()33,,n +……}，求母函数。

解：1(1)nx -的第k 项为：11()k n n +-- ，对于本题，n=4， ∴母函数为：41(1)x -2.3 已知母函数G （X ）=25431783x x x--+,求序列{ n a }解：G （X ）=)61)(91(783x x x +-+=)61()91(x Bx A ++-从而有： ⎩⎨⎧-==⇒⎩⎨⎧=-=+4778963B A B A B A G （X ）=)61(4)91(7x x +-+-G （X ）=7)999x (13322 ++++x x -4))6((-6)(-6)x (13322 +-+++x xn a =7*n )6(*49n -- 2.4．已知母函数239156xx x ---，求对应的序列{}n a 。

解：母函数为239()156x G x x x -=--39(17)(18)xx x -=+- A BG(x)17x 18xA(18x)B(17x)39x=++--++=-令 A B 38A +7B =9+=⎧⎨--⎩解得：A=2 B=1所以 ii i 0i 021G(x)2*(7x)(8x)17x 18x ∞∞===+=-++-∑∑n n n a 2*(7)8=-+2.5 设n n F G 2=，其中F n 是第n 个Fibonacci 数。

组合数学(第四版)课后习题答案

组合数学(第四版)课后习题答案

第2章 鸽巢原理2.4 练习题1、关于本节中的应用4，证明对于每一个=k 1，2，…，21存在连续若干天，在此期间国际象棋大师将恰好下完k 局棋（情形=k 21是在应用4中处理的情况）。

能否判断：存在连续若干天，在此期间国际象棋大师将恰好下完22局棋？证明：设i a 表示在前i 天下棋的总数若正好有i a =k ,则命题得证。

若不然,如下：∵共有11周，每天至少一盘棋，每周下棋不能超过12盘∴有 771≤≤i ，且13217721≤<<<≤a a a {}21,,2,1 ∈∀k 有kk a k a k a k +≤+<<+<+≤+13217721 观察以下154个整数：ka k a k a a a a +++77217721,,,,,,, 每一个数是1到k +132之间的整数，其中153132≤+k 由鸽巢原理，这154个数中至少存在两个相等的数∵7721,,,a a a 都不相等，k a k a k a +++7721,,, 都不相等∴j i ,∃，使i a =ka j +即这位国际象棋大师在第1+j ，2+j ，…，i 天总共下了k 盘棋。

综上所述，对于每一个=k 1，2，…，21存在连续若干天，在此期间国际象棋大师将恰好下完k 局棋。

□当k =22时，132+k =154，那么以下154个整数22,,22,22,,,,77217721+++a a a a a a在1到154之间。

ⅰ）若这154个数都不相同则它们能取到1到154的所有整数，必然有一个数是22∵2222>+i a ，771≤≤i ∴等于22的数必然是某个i a ，771≤≤i则在前i 天，这位国际象棋大师总共下了22盘棋。

ⅱ）若这154个数中存在相同的两个数∵7721,,,a a a 都不相等，k a k a k a +++7721,,, 都不相等∴j i ,∃，使i a =ka j +即这位国际象棋大师在第1+j ，2+j ，…，i 天总共下了k 盘棋。

小学奥数7-5-2 组合的基本应用(二).专项练习及答案解析

小学奥数7-5-2 组合的基本应用(二).专项练习及答案解析

1.使学生正确理解组合的意义；正确区分排列、组合问题；2.了解组合数的意义，能根据具体的问题，写出符合要求的组合；3.掌握组合的计算公式以及组合数与排列数之间的关系；4.会分析与数字有关的计数问题，以及与其他专题的综合运用，培养学生的抽象能力和逻辑思维能力；通过本讲的学习，对组合的一些计数问题进行归纳总结，重点掌握组合的联系和区别，并掌握一些组合技巧，如排除法、插板法等．一、组合问题日常生活中有很多“分组”问题．如在体育比赛中，把参赛队分为几个组，从全班同学中选出几人参加某项活动等等．这种“分组”问题，就是我们将要讨论的组合问题，这里，我们将着重研究有多少种分组方法的问题．一般地，从n 个不同元素中取出m 个(m n ≤)元素组成一组不计较组内各元素的次序，叫做从n 个不同元素中取出m 个元素的一个组合．从排列和组合的定义可以知道，排列与元素的顺序有关，而组合与顺序无关．如果两个组合中的元素完全相同，那么不管元素的顺序如何，都是相同的组合，只有当两个组合中的元素不完全相同时，才是不同的组合．从n 个不同元素中取出m 个元素(m n ≤)的所有组合的个数，叫做从n 个不同元素中取出m 个不同元素的组合数．记作mn C ．一般地，求从n 个不同元素中取出的m 个元素的排列数nm P 可分成以下两步： 第一步：从n 个不同元素中取出m 个元素组成一组，共有m n C 种方法；知识要点教学目标7-5-2.组合的基本应用（二）第二步：将每一个组合中的m 个元素进行全排列，共有m mP 种排法． 根据乘法原理，得到m m mn n mP C P =⋅． 因此，组合数12)112321⋅-⋅-⋅⋅-+==⋅-⋅-⋅⋅⋅⋅m mn nm m P n n n n m C P m m m （）（（）（）（）．这个公式就是组合数公式．二、组合数的重要性质一般地，组合数有下面的重要性质：m n mn nC C -=(m n ≤) 这个公式的直观意义是：m n C 表示从n 个元素中取出m 个元素组成一组的所有分组方法．n mn C -表示从n 个元素中取出(n m -)个元素组成一组的所有分组方法．显然，从n 个元素中选出m 个元素的分组方法恰是从n 个元素中选m 个元素剩下的(n m -)个元素的分组方法．例如，从5人中选3人开会的方法和从5人中选出2人不去开会的方法是一样多的，即3255C C =．规定1n n C =，01n C =．模块一、组合之几何问题【例 1】 在一个圆周上有10个点，以这些点为端点或顶点，可以画出多少不同的：⑴ 直线段；⑵ 三角形；⑶ 四边形．【考点】组合之基本运用 【难度】3星 【题型】解答【解析】 由于10个点全在圆周上，所以这10个点没有三点共线，故只要在10个点中取2个点，就可以画出一条线段；在10个点中取3个点，就可以画出一个三角形；在10个点中取4个点，就可以画出一个四边形，三个问题都是组合问题．由组合数公式：⑴ 可画出221010221094521P C P ⨯===⨯(条)直线段． ⑵ 可画出331010331098120321P C P ⨯⨯===⨯⨯(个)三角形． 例题精讲⑶ 可画出44101044109872104321P C P ⨯⨯⨯===⨯⨯⨯(个)四边形． 【答案】⑴21045C = ⑵310120C = ⑶410210C =【巩固】 平面内有10个点，以其中每2个点为端点的线段共有多少条？ 【考点】组合之基本运用 【难度】2星 【题型】解答【解析】 这道题不考虑线段两个端点的顺序，是组合问题，实际上是求从10个元素中取出2个元素的组合数，由组合数公式，2101094521C ⨯==⨯，所以以10个点中每2个点为端点的线段共有45条．【答案】45【巩固】 在正七边形中，以七边形的三个顶点为顶点的三角形共有多少个？ 【考点】组合之基本运用 【难度】2星 【题型】解答【解析】 三角形的形状与三个顶点选取的先后顺序无关，所以这是一个组合问题，实际上是求从7个点中选出3个点的选法，等于3776535321C ⨯⨯==⨯⨯(种)．【答案】3735C =【例 2】 平面内有12个点，其中6点共线，此外再无三点共线．⑴ 可确定多少个三角形？⑵ 可确定多少条射线？【考点】组合之基本运用 【难度】3星 【题型】解答 【解析】 ⑴ 分三类：①有2个顶点在共线的6点中，另1个顶点在不共线的6点中的三角形有2665669021C ⨯⨯=⨯=⨯个； ②有1个顶点在共线的6点中，另2个顶点在不共线的6点中的三角形有2665669021C ⨯⨯=⨯=⨯(个)； ③3个顶点都在不共线的6点中的三角形有3665420321C ⨯⨯==⨯⨯个．根据加法原理，可确定909020200++=个三角形．⑵ 两点可以确定两条射线，分三类：①共线的6点，确定10条射线；②不共线的6点，每两点确定两条射线，共有2665223021C ⨯⨯=⨯=⨯(条)射线；③从共线的6点与不共线的6点中各取一个点可以确定66272⨯⨯=(条)射线． 根据加法原理，可以确定103072112++=(条)射线． 【答案】⑴200 ⑵112【巩固】 如图，问：⑴ 图1中，共有多少条线段？ ⑵ 图2中，共有多少个角？54321...P 9P 3P 2P 1BAO图1 图2 【考点】组合之基本运用 【难度】1星 【题型】解答【解析】 ⑴ 在线段AB 上共有7个点（包括端点A 、B ）．注意到，只要在这七个点中选出两个点，就有一条以这两个点为端点的线段，所以，这是一个组合问题，而27C 表示从7个点中取两个不同点的所有取法，每种取法可以确定一条线段，所以共有27C 条线段． 由组合数公式知，共有227722762121P C P ⨯===⨯(条)不同的线段； ⑵ 从O 点出发的射线一共有11条，它们是OA ， 1OP ，2OP ，3OP ，，9OP ，OB ．注意到每两条射线可以形成一个角，所以，只要看从11条射线中取两条射线有多少种取法，就有多少个角．显然，是组合问题，共有211C 种不同的取法，所以，可组成211C 个角．由组合数公式知，共有2211112211105521P C P ⨯===⨯(个)不同的角． 【答案】⑴2721C = ⑵21155C =模块二、组合之应用题【例 3】 6个朋友聚会，每两人握手一次，一共握手多少次？【考点】组合之基本运用 【难度】1星 【题型】解答【解析】 这与课前挑战的情景是类似的．因为两个人握手是相互的，6个朋友每两人握手一次，握手次数只与握手的两个人的选取有关而与两个人的顺序无关，所以这是个组合问题．由组合数公式知，26651521C ⨯==⨯(次)．所以一共握手15次． 【答案】15【巩固】 某班毕业生中有20名同学相见了，他们互相都握了一次手，问这次聚会大家一共握了多少次手？【考点】组合之基本运用 【难度】1星 【题型】解答【解析】 220201919021C ⨯==⨯(次)． 【答案】220190C =【例 4】 学校开设6门任意选修课，要求每个学生从中选学3门，共有多少种不同的选法？【考点】组合之基本运用 【难度】2星 【题型】解答 【解析】 被选中的3门排列顺序不予考虑，所以这是个组合问题．由组合数公式知，3665420321C ⨯⨯==⨯⨯(种)．所以共有20种不同的选法．【答案】3620C =【例 5】 有2克，5克，20克的砝码各1个，只用砝码和一架已经调节平衡了的天平，能称出 种不同的质量。

组合数学课后习题答案

组合数学课后习题答案

第一章答案1．(a) 45 ( {1,6},{2,7},{3,8},…,{45,50} )(b) 45⨯5+(4+3+2+1) = 235( 1→2~6, 2→3~7, 3→4~8, …,45→46~50, 46→47~50, 47→48~50, 49→50 ) 2．(a) 5!8!(b) 7! P(8,5) (c) 2 P(5,3) 8! 3. (a) n!P(n+1, m) (b) n!(m+1)!(c) 2!((m+n-2)+1)! 4. 2 P(24,5) 20!5. 2⨯5⨯P(8,2)+3⨯4⨯P(8,2)6. (n+1)!-17. 用数学归纳法易证。

8. 41⨯319. 设 n=p 1n 1p 2n 2…p kn k , 则n 2的除数个数为 ( 2p 1+1) (2p 2+1) …(2p k+1).10．1）用数学归纳法可证n 能表示成题中表达式的形式；2）如果某n 可以表示成题中表达式的形式，则等式两端除以2取余数，可以确定a 1；再对等式两端的商除以3取余数，又可得a 2；对等式两端的商除以4取余数，又可得a 3；…；这说明表达式是唯一的。

11．易用C(m,n)=m!/(n!(m-n)!)验证等式成立。

组合意义：右：从n 个不同元素中任取r+1个出来，再从这r+1个中取一个的全体组合的个数；左：上述组合中，先从n 个不同元素中任取1个出来，每一个相同的组合要生复 C(n-1,r) 次。

12．考虑,)1(,)1(101-=-=+=+=∑∑n nk k k n nnk kknx n x kC x x C 求导数后有令x=1, 即知.210-==∑n nk kn n kC13. 设此n 个不同的数由小到大排列后为a 1, a 2, …, a n 。

当第二组最大数为a k 时，第二组共有2k-1种不同的可能，第一组有2n-k -1种不同的可能。

故符合要求的不同分组共有12)2()12(21111+-=-----=∑n k n k n k n 种。

计算机应用数学-(组合数学)-答案哈工大

计算机应用数学-(组合数学)-答案哈工大

1，证明，如果从集合{1，2，...，2n}中选择n+1整数，那么总存在两个整数，它们之间相差为1.2，用鸽巢原理证明，有理数m/n展开的十进制小数最终是要循环的。

例如，34 478/99 900=0.345 125 125 125 125 12...3，一间屋内有10个人，他们当中没有人超过60岁（年龄只能以整数给出）但又至少不低于1岁。

证明，总能够找出两组人（两组不含相同人），各组人的年龄和是相同的。

题中的数10能换成更小的数吗？4，一只袋子装了100个苹果、100个香蕉、100个橘子和100个梨。

如果我每分钟从袋子里了出1种水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？5，i）证明，在边长为1的等边三角形内任意选择5个点，存在2个点，其间距离至多为1/2。

ii）证明，在边长为1的等边三角形内任意选择10个点，存在2个点，其间距离至多为1/3。

iii）确定一个整数m小n，使得如果在边长为1的等边三角形内任意选择的m小n个点，则存在2个点，其间距离至多为1/n.6，下列各数各有多少互异正因子？i）3的4次方X 5的2次方X 7的6次方X 11ii）620iii）10的10次方7，确定下列类型的一手牌（5张牌）的数目。

i）full houses （3张一样大小的牌及2张相同点数的另外大小的牌）。

ii）顺牌（5张点数相连的牌）。

iii）同花（5张一样花色的牌）。

iv）同花顺（5张点数相连的同样花色的牌）。

v）恰好两个对（一对同样大小，另一对另外点数同样大小，再有一张另外大小的5张牌）。

vi）恰好一个对（一对同样大小，另外三张另外大小且互异点数的牌）。

8，从拥有10名男会员和12名女会员的一个俱乐部选出一个5人委员会。

如果至少要包含2位女士，能够有多少种方法形成这个委员会？此外，如果俱乐部还有一位特定的男士和一们特定的女士拒绝进入该委员会一起工作，形成委员会的方式又有多少？9，学校有100名学生和3个宿舍A，B和C，它们分别容纳25，35和40人。

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

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

2.1题（陈兴）求序列{ 0，1，8，27，3n }的母函数。

解：由序列可得到32333()23n G x x x x n x =+++++因为23111n x x x x x =++++++- 2311()'12341n x x x nx x-=++++++-设 2311()()'23(1)1n np x x x x x n x nx x-==++++-+-2222221[()]'123(1)n n p x x x x n x n x --=+++++-+设 2223212()[()]'23(1)n nq x x p x x x x n x n x -==++++-+3323231[()]'123(1)n n q x x x n x n x --=++++-+ 3233313[()]'23(1)n n x q x x x x n x n x -=+++-+ 由以上推理可知[()]'x q x =,[7*94*(6)],n n +-所以可通过求得[()]'x q x 得到序列的母函数：32()4G x x x x =++2321()()[34(3)]6n H x F x dx x x n x +==++++⎰2.2题（陈兴）已知序列343,,,,333n ⎧+⎛⎫⎛⎫⎛⎫⎫⎨⎬ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎭⎩，求母函数 解： 3*2*14*3*2(3)*(2)*(1)()3*2*13*2*13*2*1nn n n G x x +++=+++=1[3.2.1 4.3.2(3)(2)(1)]6n x n n n x ++++++211()()[3.2 4.3(3)(2)]6n F x G x dx x x n n x +==+++++⎰ 2321()()[34(3)]6n H x F x dx x x n x +==++++⎰3431()()[]6n I x H x dx x X x ++==++⎰因为23111n x x x x+=+++++-所以211()(1)61I x x x x=----所以31()[]'''61x G x x=-就是所求序列的母函数。

组合数学第二章习题解答

组合数学第二章习题解答

1 1 2 2 n 1 G(x) = +2 x +...(n +1) x +... 1− x 1− x 1− x
1+ x G(x) = (1− x)4
2.13已知
an = ∑k ,
3 k =1
n+1
1+ 4x + x2 ∞ = ∑(n +1)3 xn (1− x)4 n=0
求序列{an}的母函数
G(x) =1+ (1+ 23)x + (1+ 23 + 33)x2 +... + (1+ 23 +... + (n +1)3)xn +... G(x) = (1+ x + x2 +...) + 23 x(1+ x + x2 +...) +...(n +1)3 xn (1+ x + x2 +...) +...
227求下列递推关系的一般解4an1特解为两端同除以代入得特解为因此一般解为特解为两端同除以代入得特解为227求下列递推关系的一般解4an1一般解为代入替推关系的特解为hnhn一般解为代入替推关系的特解为hnhn一般解为代入替推关系的特解为按叠加原理228lnlnlnln10lnlnlnlnln代入特征根为两边求对数230lnlnlnlnln12ln代入特征根为两边求对数231是常数因此233f0f1f2是费卜拉契序列求解
第二章习题
2.3 已知序列{C(3,3),C(4,3),...,C(n+3,3),...},求母函数。
G(x) =1+ 4x +10x2 +... + C(n + 3,3)xn +... =1+ 4x +10x2 +... + C(4 + n −1 n)xn +... , = 1 (1− x)4
组合数学 第四版 (Richard A[1].Brualdi 著) 机械工业出版社作业答案

组合数学 第四版 (Richard A[1].Brualdi 著) 机械工业出版社作业答案


解法 1 因此，
对任意非负整数 n 和 k， (k 1) 即 ， ， (n 1) k k k 1 k 1 k 1 n 1 1 n 1 n 1 n 1 n 1 (1) n 2 1 3 2 4 3 n 1 n
k 1 k 1 k n 1 k 1 n 1 (1) k 0 n
w.

k 0
da
(1) k n 1 1
n 1 k 1
课
后
2n (3 (1)) n
n n nk n nk k 3 ( 1 ) k (1)k k 3 k 0 k 0
a1 , a 2 , , a 37 和 a1 13, a 2 13,, a 37 13 都是严格单调递增序列。因为总的学习时间
co
m
③ 考虑 6 位整数。最高位不能为 0，因此 8 位整数有 7 P(7, 5) 个。 ④ 考虑 5 位整数。最高位不能为 0，因此 8 位整数有 7 P (7, 4) 个。 ⑤ 考虑 4 位整数。若千位数字大于 5，有 3 P(7, 3) 个。若千位数字等于 5，则百位数字 必须大于等于 4，有 4 P(6, 2) 个。
至少已拿出 12 个相同种类的水果。因此，需要 45 分钟。 17. 证明：在一群 n 1 个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没 有人与他/她自己是熟人） 。
w.
证明 因为每个人都不是自己的熟人，所以每个人的熟人的数目是从 0 到 n 1 的整数。若 有两个人的熟人的数目分别是 0 和 n 1 ，则有人谁都不认识，有人认识所有的人，这是不 可能的。因此，这 n 个人的熟人的数目是 n 1 个整数之一，必有两个人有相同数目的熟人。
组合数学 课后答案 PDF 版

组合数学 课后答案 PDF 版

3.1 某甲参加一种会议,会上有6位朋友,某甲和其中每一个人在会上各相遇12次,每两人各相遇6次,每3人各相遇4次,每4人各相遇3次,每5人各相遇2次,每6人各相遇1次,1人也没遇见的有5次,问某甲共参加几次会议?解:设A 为甲与第i 个朋友相遇的会议集.i=1,2,3,4,5,6.则 │∪A i │=12*C(6,1)-6*C(6,2)+4*C(6,3)-3*(6,4)+2*(6,5)-C(6,6) =28甲参加的会议数为 28+5=333.2：求从1到500的整数中被3和5整除但是不能被7整除的数的个数。

解：设 A 3：被3整除的数的集合A 5：被5整除的数的集合 A 7：被7整除的数的集合 所以 ||=||-||=-=33-4=29 3.3 n 个代表参加会议，试证其中至少有2个人各自的朋友数相等解：每个人的朋友数只能取0，1，…，n －1．但若有人的朋友数为0，即此人和其 他人都不认识，则其他人的最大取数不超过n －2．故这n 个人的朋友数的实际取数只 有n －1种可能．，根据鸽巢原理所以至少有２人的朋友数相等．3.4试给出下列等式的组合意义0j j 0(1)=(1), 1n-m-j+1(2)(1)1 j 1(3)...(1) 1 12m l l n m l n m m n l n k m n k l k l n m l n m l m l m l m l m l m l m m m m m l =-=--⎛⎫⎛⎫⎛⎫-≥≥ ⎪ ⎪⎪-⎝⎭⎝⎭⎝⎭---⎛⎫⎛⎫⎛⎫=- ⎪ ⎪⎪--⎝⎭⎝⎭⎝⎭+-++++⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫=-+-+- ⎪ ⎪ ⎪ ⎪ ⎪-+++⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭∑∑ 证明：（1）从n 个不同元素中取k ，使得其中必含有m 个特定元素的方案数为)()(kn mn m k mn --=--。

设这m 个元素为a 1,a 2,…,a m , Ai 为包含a i 的组合（子集），i=1,…,m.1212|...|(...)12 =(...(1))1 2 =(1) m m m l n A A A A A A k n m n m n m n m k k k m k m n l l k ⎛⎫=- ⎪⎝⎭---⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫--++- ⎪ ⎪⎪ ⎪⎪ ⎪⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭-⎛⎫⎛- ⎪⎝⎭ 0ml =⎫ ⎪⎝⎭∑ （2）把l 个无区别的球放到n 个不同的盒子，但有m 个空盒子的方案数为11n l m n m -⎛⎫⎛⎫⎪⎪--⎝⎭⎝⎭令k=n-m ，设A i 为第i 个盒子有球，i=1，2，…k12k 121|...|(...)1k 11211 =(...(1)) 1 2 k k k l A A A A A A k k l k l k k l k k k l k l l k l +-⎛⎫=- ⎪⎝⎭+--+--+--+-⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫⎛⎫--++- ⎪ ⎪⎪ ⎪⎪ ⎪⎪⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭⎝⎭ kj j 0k k-j+1 =(1)j l l =-⎛⎫⎛⎫- ⎪⎪⎝⎭⎝⎭∑ （3）设A i 为m+l 个元素中去m+i 个，含特定元素a 的方案集；N i 为m+l 个元素中取m+i 个的方案数。

卢开澄组合数学--组合数学第二章习题解答精品文档35页

卢开澄组合数学--组合数学第二章习题解答精品文档35页

（b）求序列an与bn的母函数。
（c）用Fibonacci数来表示 a n 与 b n 。
解：...
28. 设 F 1 F 2 1 ,F 1 F n 1 F n 2
（a）证明
F n F k F n k 1 F k 1 F n k , n k 1 （b）证明 Fn Fm 的充要条件是 n m 。
解：...
9.利用 11221231262 ，
改善 §4(2) 的 p n估计式。
解：...
10. 8台计算机分给3个单位，第1单位 的分配量不超过3台，第2单位的分配量 不超过4台，第3个单位不超过5台，问 共有几种分配方案？
解：...
11. 证明正整数n都可以唯一地表示成不 同的且不相邻的Fibonacci数之和。即
（c）证明
FmFn Fmn2 Fmn6 Fmn10
FFmmnn21
当n是奇数， 当n是偶数。
mn2.
（d）证明(F m ,F n ) F (m ,n ),(m ,n )为m,n
的最大公约数。
解：...
29. 从1到n的自然数中选取k个不同且不
相邻的数，设此选取的方案为 f(n,k)。 （a）求 f(n,k)的递推关系。
解：...
22. 求矩阵 3 1100 . 0 2
解：...
23. 求
n
n
Sn k(k1), Sn k(k2),
k0
k0
n
Sn k(k1)(k2).
k0
解：...
24. 在一个平面上画一个圆，然后一条 一条地画n条与圆相交的直线。当r是大 于1的奇数时，第r条直线只与前r-1条直 线之一在圆内相交。当r是偶数时，第r 条直线与前r-1条直线在圆内部相交。如 果无3条直线在圆内共点，这n条直线把 圆分割成多少个不重叠的部分？
组合数学_第2章

组合数学_第2章


xi
1i n
ln xi e exp( ln xi ) 1i n
第二章 基本计数原理 即积式可转化为和式来处理。条件xi＞0并无实质性的限制，因 若 某 个 xi=0 ， 则 整 个 积 式 为 0 ， 又 恰 有 k 项 取 负 时 ， 可 先 对 （2.1.8）式两边乘(-1)k，以确保xi＞0， 最后再将其恢复过来。
第二章 基本计数原理 2.2.2 乘法原理(Multiplication Principle) 设 A， B为二不同类事件，若事件A有m种产生方式，事件B 有n种产生方式，则“事件A与事件B”有mn种产生方式 用集合论的术语，乘法原理也可描述如下： 设S，T为二集，若S为m元集，T为n元集，则S与T的叉积之 集合S×T为mn元集。 推广的乘法原理是：如果Ti为ni元集(i=1, 2, …, r)，则
0i k
a a
2i j 0
k
2j
第二章 基本计数原理 3. 双下标
( a11 a12 a1n ) ( a21 a22 a2 n ) ( am1 am 2 amn )
1 j n
a
1j
a2 j
iN n
a
i
第二章 基本计数原理 命题 1 用和号∑表示的和式中，通项下标的改变不影响和 式。 例如
0i n
a , a 及 a
i 0 j n j 0 k n
k
都表示同一和式。 当通项下标不取连续整数时，也希望能寻找一些规律，以 便于用和式写出简单的表示式，下面给出一些特殊和式的例子。
第二章 基本计数原理 · 对（2.1.9）式的算法 №1 输入N №2 M 1；（累乘器M置1） №3 对k=2, N, 做

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

第二章 容斥原理与鸽巢原理1、1到10000之间（不含两端）不能被4，5和7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，则 |A|=10000.记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除的整数集合，则有：|A 1| = L 10000/4」=2500,|A 2| = L 10000/5」=2000,|A 3| = L 10000/7」=1428,于是A 1∩A 2 表示A 中能被4和5整除的数,即能被20 整除的数，其个数为| A 1∩A 2|=L 10000/20」=500；同理， | A 1∩A 3|=L 10000/28」=357,| A 2∩A 3|=L 10000/35」=285,A 1 ∩A 2 ∩ A 3 表示A 中能同时被4,5,7整除的数，即A 中能被4,5,7的最小公倍数lcm(4,5,6)=140整除的数，其个数为| A 1∩A 2∩A 3|=L 10000/140」= 71.由容斥原理知，A 中不能被4，5，7整除的整数个数为||321A A A ⋂⋂= |A| - (|A 1| + |A 2| +|A 3|) + (|A 1∩A 2| + |A 1∩A 3| +|A 3∩A 2|) - |A 1∩A 2∩A 3| = 51432、1到10000之间（不含两端）不能被4或5或7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除的整数集合，A 中不能被4，5，7整除的整数个数为||321A A A ⋃⋃ = |A| - ||321A A A ⋂⋂ - 2 = 10000 - L 10000/140」- 2 = 99273、1到10000之间（不含两端）能被4和5整除，但不能被7整除的整数有多少个？解 令A 1表示在1与10000之间能被4和5整除的整数集，A 2表示4和5整除，也能被7整除的整数集。

《组合数学》第二版(姜建国著)-课后习题答案全

习题一（排列与组合）1．在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？ 解：该题相当于从“1，3，5，7，9”五个数字中分别选出1，2，3，4作排列的方案数；（1）选1个，即构成1位数，共有15P 个； （2）选2个，即构成两位数，共有25P 个； （3）选3个，即构成3位数，共有35P 个； （4）选4个，即构成4位数，共有45P 个；由加法法则可知，所求的整数共有：12345555205P P P P +++=个。

2．比5400小并具有下列性质的正整数有多少个？ （1）每位的数字全不同；（2）每位数字不同且不出现数字2与7； 解：（1）比5400小且每位数字全不同的正整数； 按正整数的位数可分为以下几种情况：① 一位数，可从1～9中任取一个，共有9个；② 两位数。

十位上的数可从1～9中选取，个位数上的数可从其余9个数字中选取，根据乘法法则，共有9981⨯=个；③ 三位数。

百位上的数可从1～9中选取，剩下的两位数可从其余9个数中选2个进行排列，根据乘法法则，共有299648P ⨯=个；④ 四位数。

又可分三种情况：⏹ 千位上的数从1～4中选取，剩下的三位数从剩下的9个数字中选3个进行排列，根据乘法法则，共有3942016P ⨯=个；⏹ 千位上的数取5，百位上的数从1～3中选取，剩下的两位数从剩下的8个数字中选2个进行排列，共有283168P ⨯=个；⏹ 千位上的数取5，百位上的数取0，剩下的两位数从剩下的8个数字中选2个进行排列，共有2856P =个；根据加法法则，满足条件的正整数共有：9816482016168562978+++++=个；（2）比5400小且每位数字不同且不出现数字2与7的正整数；按正整数的位数可分为以下几种情况：设{0,1,3,4,5,6,8,9}A = ① 一位数，可从{0}A -中任取一个，共有7个；② 两位数。

十位上的数可从{0}A -中选取，个位数上的数可从A 中其余7个数字中选取，根据乘法法则，共有7749⨯=个；③ 三位数。

组合数学答案2-5


2. Prove that for any n+1 integers a1, a2, …, an+1 there exist two of the integers ai and aj with i ≠ j such that ai - aj is divisible by n.
Proof: Suppose that we divide all the integers by n, the remainders are {0, 1, …, n-1}.不是 1 到 n-1. According to Pigeonhole Principal, for n+1 integers, there exit two integers have the same remainders when divided by n. Assume that they are ai and aj, it is obvious that ai - aj is divisible by n, because they have the same remainder.
第一次作业 第二章 鸽巢原理
1. Show that if n+1 integers are chosen from the set {1, 2, …, 3n}, then there are always two which differ by 1 or 2.
Proof: Suppose that we partition set {1, 2, …, 3n} into {1, 2, 3}, {4, 5, 6}, …, {3n-2, 3n-1, 3n} and choose n+1 integers from the n sets. According to the Pigeonhole Principal, there are at least two integers from the same set. And elements in the same set differ by 1 or 2. Therefore, we concluded t hat if n+1 integers are chosen from the set {1, 2, …, 3n}, there are always two which differ by 1 or 2.

组合数学 第2章习题解答

2 n
( a )G
2
= (1 − x )
−4
= ∑ C ( n + 3,3) x n
n=0
∞
2.4 已知母函数 1 − x − 56 x 2，求对应的序列
注意到 1－x-56x2=(1-8x)(1+7x)， 用A/(1-8x)+B/(1+7x)的分子等于3-9x 待定A，B的方程组为： A + B = 3 7 A − 8 B = −9 解出A＝1，B＝2 G(x)=1/(1-8x)+2/(1+7x) 利用基本母函数1/(1-x) an=8n-7n
• 解：G(x)=/Sum{0,n}(anxn) • 参考p61，例2－13，2－14， • 参考p111， 例2－63
2.48有红、黄、蓝、白球各两个，绿、紫、黑球各3个， 问从中取出10个球，试问有多少种不同的取法？ 用指数型母函数，可得母函数 x x2 4 x x 2 x3 3 G ( x) = (1 + + ) ⋅ (1 + + + ) 1! 2! 1! 2! 3!
• 用多项式除法，解出a0，a1均为1
1− x + x
2
1 1
1 1 −x x2
2
• P68 x −x • 将(1-x+x2)分解因子，转化为基本母函数.引 用P59，定理2－1. 并参考p56例子2－11. • 这个题目整体都做的不错

2.18（1）课练，用母函数法求 an-6an-1+8an-2=0
注：这个题目中有同学使用的符号 n指代比较 混乱。虽然最后结果对，但过程中未体现出逻 辑的连贯性。 也有同学用积分和求导渐次推理得到正确结论。 十分可贵。不过有的人在最后写有一个 m次方， 令人困惑
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

7! 2!(7−2)!
=
7! 2!5!
and C (7, 5) =
7! 5!(7−5)!
=
7! 5!2! ;
8 7(b). C (6, 4) =
6! 4!(6−4)!
Answers to Selected Exercises =
6! 4!2!
and C (6, 2) =
6! 2!(6−2)!
=
6! 2!4! ;
n+1 2
× 3 × 10−9 . × 3 × 10−11 .
8(a). n × 3 × 10−11 . 8(b).
n+1 2
Section 2.5 . 1(a). 3 · 2; 1(b). 5 · 4 · 3; 1(c). 8 · 7 · 6 · 5 · 4; 1(d). 0; 2(a). 63 ; 2(b). 6 · 5 · 4; 2(c). 1 · 6 · 6; 2(d). 1 · 5 · 4; 3(a). 84 ; 3(b). 8 · 7 · 6 · 5; 3(c). 1 · 8 · 8 · 8;
8. 1 7 21 35 35 21 7 1; 9. C (5, 3) =
5! 3!2!
= 10, C (4, 2) =
4! 2!2!
= 6, C (4, 3) =
4! 3!1!
= 4, and 10 = 6 + 4; = 6, and 21 = 15 + 6;
10. C (7, 5) =
7! 5!2!
4
Answers to Selected Exercises
Applied Combinatorics
by Fred S. Roberts and Barry Tesman
Answers to Selected Exercises1
Chapter 2
Section 2.1 . 1. yes: 263 < 20, 000; 2. yes: 263 · 103 > 5, 000; 3(a). 31 + 32 + 33 ; 3(b). 31 + 32 + 33 + 34 ; 3(c). 2 · 33 ; 4. 83 × 105 ; 8 × 2 × 10 × 83 × 105 ; 5. n = 5 since 21 + 22 + 23 + 24 = 30 and 21 + 22 + 23 + 24 + 25 = 62. 6. 2mn ; 7. (2 · 2 · 2 · 2 · 3) − 1; 8. 106 − 96 ; 9. Bit string x S1 (x) S2 (x) S3 (x) S4 (x) 00 0 0 0 0 10 0 0 0 0 10 0 0 1 1 11 0 1 0 1 Bit string x S9 (x) S10 (x) S11 (x) S12 (x) 00 1 1 1 1 10 0 0 0 0 10 0 0 1 1 11 0 1 0 1 10. 22
2n
S 5 ( x) S 6 ( x) S 7 ( x) S 8 ( x) 0 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 S13 (x) S14 (x) S15 (x) S16 (x) 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1
1 More solutions to come. Comments/Corrections would be appreciated and should be sent to: Barry Tesman (tesman@) or Fred Roberts (froberts@).
6 9. 5! · 5! vs. 10!. Section 2.4 . 1. 25! · 2. 25! ·
1 109 1 1011
Answers to Selected Exercises
· ·
1 3.15×107 1 3.15×107
≈ 4.9 × 108 years. ≈ 4.9 × 106 years.
7
7(a). 28 . There are 23 = 8 subsets of A and each subset can be assigned a 0 or 1; 7(b). 22 ; 8(a). 22 ; 8(b). 22 . Section 2.7 . 1. C (10, 5); 2. C (50, 7); 3(a). 3(b). 3(c).
6! 3!(6−3)! 7! 4!3! 5! 1!4!
n 3 n
= 20;
= 35; = 5;
3(d). 0; 4. 5.
n! 1!(n−1)! 5! 2!3!
= n;
= 10; {a, b}, {a, c}, {a, d}, {a, e}, {b, c}, {b, d}, {b, e}, {c, d}, {c, e}, {d, e};
6! 6. 2!4! = 15; {a, b}, {a, c}, {a, d}, {a, e}, {a, f }, {b, c}, {b, d}, {b, e}, {b, f }, {c, d}, {c, e}, {c, f }, {d, e}, {d, f }, {e, f };
7(a). C (7, 2) =
Answers to Selected Exercises 3(d). 1 · 6 · 5 · 1; 4. P (20, 5); 5(a). 9 × 9 × 8 × 7; 5(b). 4088. There are 1 × 9 × 8 × 7 extensions if the first digit is 1 and there are 8 × 8 × 8 × 7 extensions if the first digit is 2 - 9; 6. 403 = 64, 000. Section 2.6 . 1. {}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}; 2. 235 ; 3. 27 ; 5. 210 −ted Exercises 11. 22
n−1
5
;
12. 2p ; 2p − 1; 13(a). 2m 2p−m ; 13(b). 2m−1 2p−m ; 13(c). (2m − 1) · 2p−m ; 14(a). 3 · 2 · 3; 14(b). 23·2·3 . Section 2.2 . 1. 23 + 24 + 25 ; 2. (8 · 7) + (8 · 12) + (7 · 12); 3. 55 + 45 ; 4. Yes: 1015 > 10, 000, 000; No: 215 < 10, 000, 000; 5. 264 + 255 ; 6. 2 + 3; 7. (7 · 3)30 ; 8. 33 + 3 · 43 . Section 2.3 . 1(a). 123, 132, 213, 231, 312, 321; 1(b). 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321; 2. 1 · 4 · 3 · 2 · 1; 3. 1 · n − 2 · n − 3 · · · · · 2 · 1 · 1; 4(b). s6 ≈ 710 vs. 6! = 720; 5. 2 · 3 · 2 · 1 = 12; 6(a). 4 · 1 · 3 · 2 · 1; 6(b). n − 2 · 1 · 1 · n − 3 · n − 4 · · · · · 2 · 1; 7. 1 · 3 · 2 · 1 · 1; 8(a). 3 · 3 · 2 · 2 · 1 · 1; 8(a). n · n · n − 1 · n − 1 · · · · · 2 · 2 · 1 · 1;
3. There are n! schedules. Each committee in each schedule must be checked to see if it received its first choice - this takes n steps per schedule. The computational complexity is f (n) = n · n!; 5. We will start (and end) at 1. Total cost Order 1 2 3 4 1 1+ 3+ 11+8 = 23 12431 1+ 6+ 2+ 4 = 13 8+ 9+ 6+ 8 = 31 13241 1 3 4 2 1 8+ 11+ 3+ 16= 38 1 4 2 3 1 11+ 3+ 3+ 4 = 21 1 4 3 2 1 11+ 2+ 9+ 16= 38 6. best order is 2, 3, 1; 7(a). n × 3 × 10−9 . 7(b).
= 21, C (6, 4) =
6! 4!2!
= 15, C (6, 5) =
6! 5!1!
11(a). C (8, 4); 11(b). C (8, 4)/2; 11(c). 28 − 2; 12. C (6, 3) + C (6, 2) + C (6, 1) + C (6, 0); 13(a). C (10, 5); 13(b). 210 − 2; 14. C (21, 5)C (5, 3)8! + C (21, 4)C (5, 4)8! + C (21, 3)C (5, 5)8!; 15. Calculate the sum of those odd numbers with distinct digits with no 0’s, a 0 in the tens place, or a 0 in the hundreds place. No 0’s: 5 choices for the ones place, then 8 · 7 · 6 choices for the other three places; 0 in the tens place: 5 choices for the ones place and 1 choice for the tens place, then 8 · 7 choices for the other two places; 0 in the hundreds place: 5 choices for the ones place and 1 choice for the hundreds place, then 8 · 7 choices for the other two places; (5 · 8 · 7 · 6) + (5 · 1 · 8 · 7) + (5 · 1 · 8 · 7) = 2240; 16(a). C (7, 3) · C (4, 2); 16(b). C (7, 1) · C (4, 1) + C (7, 2) · C (4, 2) + C (7, 3) · C (4, 3) + C (7, 4) · C (4, 4); 16(c). C (10, 3); 16(d). C (7, 2) · C (4, 2) − C (6, 1) · C (3, 1); 17(a)(i). C (9, 4); 17(a)(ii). 6; 17(a)(iii). 2; 17(a)(iv). 1; 17(b). JAVA, JAVA, JAVA, JAVA, JAVA, C++, C++, C++, C++; 17(c)(i). 9!; 17(c)(ii). 6 · 4! · 5!; 17(c)(iii). 2 · 4! · 5!; 17(c)(iv). 5 · 4 · 4 · 3 · 3 · 2 · 2 · 1 · 1;