当前位置：文档库 › 组合数学作业答案解析

组合数学作业答案解析

第二章作业答案

7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。

证明用100分别除这52个整数，得到的余数必为0, 1,…, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，…，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a 和b 。若a 和b 被100除余数相同，则b a -能被100整除。若a 和b 被100除余数之和是100，则b a +能被100整除。

11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。证明设从第一天到第i 天她共学习了i a 小时。因为她每天至少学习1小时，所以

3721,,,a a a 和13,,13,133721+++a a a 都是严格单调递增序列。因为总的学习时间

不超过

小时，所以6037≤a ，731337≤+a 。3721,,,a a a ,

13,,13,133721+++a a a 是1和73之间的74个整数，由鸽巢原理知道，它们中存在相

同的整数，有i a 和13+j a 使得13+=j i a a ，13=-j i a a ，从第1+j 天到第i 天她恰好学习了13小时。

14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？解由加强形式的鸽巢原理知道，如果从袋子中取出451)112(4=+-?个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。

17. 证明：在一群1>n 个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。证明因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到1-n 的整数。若有两个人的熟人的数目分别是0和1-n ，则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n 个人的熟人的数目是1-n 个整数之一，必有两个人有相同数目的熟人。

第三章作业答案

6. 有多少使下列性质同时成立的大于5400的整数？ (a) 各位数字互异。 (b) 数字2和7不出现。

解因为只能出现数字0, 1, 3, 4, 5, 6, 8, 9，所以整数的位数至多为8。

① 考虑8位整数。最高位不能为0，因此8位整数有)7,7(7P ?个。 ② 考虑7位整数。最高位不能为0，因此8位整数有)6,7(7P ?个。 ③ 考虑6位整数。最高位不能为0，因此8位整数有)5,7(7P ?个。 ④ 考虑5位整数。最高位不能为0，因此8位整数有)4,7(7P ?个。

⑤ 考虑4位整数。若千位数字大于5，有)3,7(3P ?个。若千位数字等于5，则百位数字必须大于等于4，有)2,6(4P ?个。根据加法原理，符合条件的整数的个数为

94830)2,6(4)3,7(3)4,7(7)5,7(7)6,7(7)7,7(7=?+?+?+?+?+?P P P P P P

8. 15人围坐一个圆桌。如果B 拒绝挨着A 坐，有多少种围坐方式？如果B 只拒绝坐在A 的右侧，又有多少种围坐方式？

解 15人围坐一个圆桌，有!14种围坐方式。若B 固定坐在A 的左侧，则可将BA 看作一个整体，有!13种围坐方式。若B 固定坐在A 的右侧，则可将AB 看作一个整体，有!13种围坐方式。因此，B 不挨着A 坐的围坐方式有!1312!132!14?=?-种，B 不坐在A 的右侧的围坐方式有!1313!13!14?=-种。

11. 从15个球员的集合中选人组成11个球员的足球队，其中5人只能踢后卫，8人只能踢边卫，2人既能踢后卫又能踢边卫。假设足球队有7个人踢边卫4个人踢后卫，确定足球队可能的组队方法数。

解设甲和乙既能踢后卫又能踢边卫。

若甲和乙均不入选，组队方法数为???? ??78????

??45。

若甲和乙均入选，组队方法数为???? ??78???? ??25+?

? ??68???? ??35+???? ??58???

??45。若甲入选且乙不入选，组队方法数为???? ??78???? ??35+?

? ??68???

??45。若乙入选且甲不入选，组队方法数也为???? ??78???? ??35+???? ??68???

??45。

因此，组队方法数总共为

???? ??78???? ??45+???? ??78???? ??25+???? ??68???? ??35+???? ??58????

??45+???

? ?????? ?????? ??+???? ?????? ???456835782=1120

21. 一位秘书在距离家以东9个街区、以北7个街区的一座大楼里工作。每天他都要步行

16个街区去上班。

(a) 对他来说可能有多少不同的路线？ (b) 如果在他家以东4个街区、以北3个街区开始向东方向的街区在水下（而他又不会游泳），则有多少条不同的路线？

解 (a) 用E 表示向东步行1个街区，用N 表示向北步行1个街区。因为该秘书需要向东步行9个街区，向北步行7个街区，总共步行16个街区，因此他的上班路线是多重集

}7,9{N E ??的排列。这样的排列的个数为

7!9!

1611440。 (b) 若他从水下的街区走过，则他先要走到离家以东4个街区、以北3个街区的地方，再

向东走一个街区，最后走到工作的大楼。他从家走到离家以东4个街区、以北3个街区的地方的路线的数目是多重集}3,4{N E ??的排列数，即

3!4!

735。他从离家以东5个街区、以北3个街区的地方走到工作的大楼的路线的数目是多重集}4,4{N E ??的排列数，即

4!4!

870。所以，如果他从水下的街区走过，则他可能有的路线数是24507035=?。因此，如果他不从水下的街区走过，则他可能有的路线数是8990245011440=-。 26. 确定多重集}5,4,3{c b a S ???=的10-排列的个数。解 S 的有1个a ，4个b ， 5个c 的10-排列的个数为

1260!

5!4!1!

10=。

S 的有3个a ，2个b ， 5个c 的10-排列的个数为

2520!

5!2!3!

10=。

S 的有3个a ，4个b ，3个c 的10-排列的个数为

4200!

3!4!3!

10=。

S 的有2个a ， 3个b ， 5个c 的10-排列的个数为

2520!

5!2!3!

10=。

S 的有2个a ， 4个b ， 4个c 的10-排列的个数为

3150!

4!4!2!

10=。

S 的有3个a 3个b 4个c 的10-排列的个数为

4200!

3!4!3!

10=。

S 的10-排列的个数为17850315042002252021260=+?+?+。

31. 方程304321=+++x x x x 有多少满足21≥x ，02≥x ，53-≥x ，84≥x 的整数解？解进行变量代换：

211-=x y ，22x y =，533+=x y ，844-=x y

则方程变为

254321=+++y y y y

原方程满足条件的解的个数等于新方程的非负整数解的个数。新方程的非负整数解的个数为

3276!326

27283282528251425=??=???

? ??=???? ??=???? ??-+ 第五章作业答案

8. 用二项式定理证明

n n

k k n

k n -=∑???? ??-=

3)1(20

证明由二项式定理知道

∑=-???

? ??=

k k k n n

y x k n y x 0)( 令3=x ，1-=y 得

∑∑=-=-???? ??-=-???? ??=-+=n

k k n k n

k k k n n

k n k n 003)1()1(3))1(3(2 18. 求和

???

? ??+-++???? ??-???? ??+???? ??-n n n n n n n 11)1(3412311211 解法1 对任意非负整数n 和k ，???? ??+=???? ??+++k n n k n k )1(11)1(，即???

? ??+=???? ??+++k n k k n n 111111，因此，

???

? ??+-++???? ??-???? ??+???? ??-

n n n n n n n 11)1(3412311211

∑∑∑+=-==???? ??+-+=???? ??+++-=???? ??+-=11

1001)1(11111)1(1

)1(n k k n k k n k k k n n k n n k n k

11110111)1(111)1(1110

11+=++=++???? ??+-+-=???? ??+-+-=∑∑+=+=n n n k n n k n n n k k n k k 解法2 由二项式定理知道

∑=???? ??-=

-n

k k

k n

x k n x 0)1()1( 两边分别求积分得

1)01(1)11()1(111

+=+-++--=-++?n n n dx x n n n

∑?∑==???

??+-=???? ??-n

k k

k k n k dx x k n 0

1001

)1()1( 所以

1111)1(3412311211+=???

? ??+-++???? ??-???? ??+???? ??-n n n n n n n n 20. 求整数a ，b 和c ，使得对所有的m

???

??+???? ??+???? ??=1233m c m b m a m

求级数的和3

321n ++++ 。

解令1=m ，???? ??+???? ??+????

??=11213113c b a ，因为02131=???

? ??=???? ??，所以1=c 。

令2=m ，???? ??+???? ??+???? ??=12223223c b a ，因为032=????

??，所以628=-=c b 。

令3=m ，????

??+???? ??+???? ??=13233333c b a ，所以63327=--=c b a 。

∑∑∑∑====????

??+???? ??+???? ??==++++n m n m n

m n

m m m m m n 000033

12636321

???

??++???? ??+=???? ??++???? ??++???? ??+=2142621316416n n n n n

)1(2)1(!4)1()1)(2(62

2+=

++-++=n n n n n n n n 25．应用组合学论证方法，证明二项式系数的Vandermonde 卷积：对所有的正整数1m ，2m 和n ，

????

??+=???? ??-???? ?

?∑=n m m k n m k m n

k 21021

作为特殊情形，推导恒等式（5-11）。

证明设B A S ?=，?=?B A ，1||m A =，2||m B =，则21||m m S +=。我们可以从集合A 中取出k 个元素，再从集合B 中取出k n -个元素，把它们合起来构成S 的有n 个元素的子集。因为A 的有k 个元素的子集有???

??k m 1个，因为B 的有k n -个元素的子集有???

??-k n m 2个，所以S 的有n 个元素的子集个数为∑=???? ??-???? ??=????

??+n k k n m k m n m m 02121。 37. 在94321)22(x x x x -+-的展开式中2

33231x x x x 的系数是什么？解由多项式定理知道

∑

=+++???

? ??=

+++n

n n n n n n n n n

x x x x n n n n n x x x x 43214

321432143214321)( 令2x 为2x -，3x 为32x ，4x 为42x -，n 为9，得到

∑

=+++--???

? ??=

-+-9

432143219

432143214

433221)2(2)1(9)22(n n n n n n n n n n n x x x x n n n n x x x x 因此，2

33231x x x x 的系数是 40320!2!1!3!3)8(!9)2(2)1(2133923-=???-?=-??-????

? ?? 42. 用牛顿二项式定理近似计算3

/110

。

解 3/13/13/1)25.01(2)28(10+=+=

)416416135323116121323141311(24

12431031∑∑∞=∞

=???? ??+????+???-?+?=???? ??=k k k k k k

1547.2)64

6135323116121323141311(2103/1≈????+???-?+?≈

第六章作业答案

3. 求出从1到10000既不是完全平方数也不是完全立方数的整数个数。

解设S 是从1到10000的整数的集合，1A 是从1到10000的完全平方数的集合，2A 是从1到10000的完全立方数的集合。因为100001002

=，所以100||1=A 。因为

33221064810000926121=<<=，所以21||2=A 。因为一个整数既是完全平方数也是

完全立方数的充分必要条件是它是完全六次方数，6

5156251000040964=<<=，所以

4||21=?A A 。从1到10000既不是完全平方数也不是完全立方数的整数个数

98834)21100(10000||)||||(||||212121=++-=?++-=?A A A A S A A

6. 面包店出售巧克力的、肉桂的和素的炸面包圈，并在一特定时刻有6个巧克力、6个肉桂和3个素炸面包圈。如果一个盒子装12个面包圈，那么可能有多少种不同的盒装面包圈组合？

解用a ，b ，c 分别表示巧克力的、肉桂的和素的炸面包圈。本题要求的是多重集

}3,6,6{c b a T ???=的12-组合的个数。设S 为},,{*c b a T ?∞?∞?∞=的所有12-组合的集合，则911214121312||=?

??=????

??-+=S 。设1A 为*T 的所有至少有7个a 的12-组合的集合，2A 为*T 的所有至少有7个b 的12-组合的集合，3A 为*T 的所有至少有4个c 的12-组合的集合。每个*T 的5-组合再加上7个a 就得到一个至少有7个a 的12-组合，所以*T 的至少有7个a 的12-组合的个数等于*T 的5-组合的个数，

21575135||1=???? ??=???? ??-+=A 。同样可得到21575135||2=????

??=???? ??-+=A ，

458108138||3=???

? ??=???? ??-+=A 。*T 的至少有7个a 和7个b 的12-组合的个数0||21=?A A ，*T 的至少有7个a 和4个c 的12-组合的个数3||31=?A A ，*T 的至

少有7个b 和4个c 的12-组合的个数3||32=?A A ，*T 的至少有7个a 、7个b 和4

个c 的12-组合的个数0||321=??A A A 。因此，T 的12-组合的个数 ||321A A A ??

||||||||)||||||(||321323121321A A A A A A A A A A A A S ??-?+?+?+++-=

100330)452121(91=-+++++-=

9. 确定方程

204321=+++x x x x

满足

611≤≤x ， 702≤≤x ， 843≤≤x ， 624≤≤x

的整数解的个数。解引入新变量

116x y -= 227x y -= 338x y -= 446x y -=

则方程

204321=+++x x x x

满足

611≤≤x ， 702≤≤x ， 843≤≤x ， 624≤≤x

的整数解的个数等于方程

74321=+++y y y y

满足

501≤≤y ， 702≤≤y ， 403≤≤y ， 404≤≤y

的整数解的个数。设S 是方程74321=+++y y y y 的所有非负整数解的集合，则

1207107147||=???

? ??=???? ??-+=S 。设1A 为方程74321=+++y y y y 的所有满足61≥y 的

非负整数解的集合，2A 为方程74321=+++y y y y 的所有满足82≥y 的非负整数解的集合，3A 为方程74321=+++y y y y 的所有满足53≥y 的非负整数解的集合，4A 为方程74321=+++y y y y 的所有满足54≥y 的非负整数解的集合，则4||1=A ，0||2=A ，

10352142||||43=???

? ??=???? ??-+==A A 。若j i ≠，则?=?j i A A 。因此，方程

74321=+++y y y y

满足

501≤≤y ， 702≤≤y ， 403≤≤y ， 404≤≤y

的整数解的个数

96101004120||||||||||||43214321=----=----=???A A A A S A A A A

24. 把六个非攻击型车放到具有如下所述禁止位置的6行6列棋盘上的方法数是多少？ (c)

解禁放位置可分成两个“独立”部分，左上角的1F 部分，包含5个位置，右下角的2F 部分，包含3个位置。用k r 表示把k 个非攻击型车都放在禁止位置的方法数。81=r 。若在1F 部分的禁止位置放两个非攻击型车，则有6123=++种方法；若在2F 部分的禁止位置放两个非攻击型车，则有1种方法；若在1F 部分和2F 部分的禁止位置各放一个非攻击型车，则有1535=?种方法。因此，2215162=++=r 。若在1F 部分的禁止位置放两个非攻击型车，在2F 部分的禁止位置放一个非攻击型车，则有1836=?种方法；若在2F 部分的禁止位置放两个非攻击型车，在1F 部分的禁止位置放一个非攻击型车，则有551=?种方法；若在1F 部分的禁止位置放三个非攻击型车，则有1种方法。因此，2415183=++=r 。若在1F 部分的禁止位置放三个非攻击型车，在2F 部分的禁止位置放一个非攻击型车，则有

331=?种方法；若在1F 部分和2F 部分的禁止位置各放两个非攻击型车，则有616=?种

方法。因此，9634=+=r 。若在1F 部分的禁止位置放三个非攻击型车，在2F 部分的禁止位置放两个非攻击型车，则有1种方法，15=r 。把六个非攻击型车放到具有上述禁止位置的6行6列棋盘上的方法数是

!1!2!3!4!5!654321?-?+?-?+?-r r r r r

16112962424221208720=-?+?-?+?-=

26. 计算}6,5,4,3,2,1{的排列654321i i i i i i 的个数，其中

3,2,11≠i ； 12≠i ； 13≠i ； 6,55≠i 以及6,56≠i 。

解所要求的排列个数等于把六个非攻击型车放到具有如下所述禁止位置的6行6列棋盘上的方法数。

禁放位置可分成两个“独立”部分，左上角的1F 部分，包含5个位置，右下角的2F 部分，包含4个位置。用k r 表示把k 个非攻击型车都放在禁止位置的方法数。91=r 。若在1F 部分的禁止位置放两个非攻击型车，则有4种方法；若在2F 部分的禁止位置放两个非攻击型车，则有2种方法；若在1F 部分和2F 部分的禁止位置各放一个非攻击型车，则有2045=?种方法。因此，2620242=++=r 。若在1F 部分的禁止位置放两个非攻击型车，在2F 部分的禁止位置放一个非攻击型车，则有1644=?种方法；若在2F 部分的禁止位置放两个非攻击型车，在1F 部分的禁止位置放一个非攻击型车，则有1052=?种方法。因此，

2415183=++=r 。若在1F 部分和2F 部分的禁止位置各放两个非攻击型车，则有824=?种方法。因此，84=r 。05=r 。把六个非攻击型车放到具有上述禁止位置的6

行6列棋盘上的方法数是

!1!2!3!4!5!654321?-?+?-?+?-r r r r r

124102862624261209720=?-?+?-?+?-=

27. 8个女孩围坐在旋转木马上。她们可以有多少种方法改变座位，使得每个女孩前面的女孩都与原先的不同？

解令S 为}8,7,6,5,4,3,2,1{的全部!7个循环排列的集合，i A 为出现模式)1(+i i 的循环排列的集合（71≤≤i ），8A 为出现模式81的循环排列的集合。若71≤≤k 且k i i ,,1 是集合}8,7,6,5,4,3,2,1{中的不同整数，则!)7(||1

k A A k

i i -=?? 。1||

== i i A 。因此，

16251!078!168!258!348!438!528!618!7||81=+???

??-???? ??+???? ??-???? ??+???? ??-???? ??+???? ??-=??A A 她们可以有1625种方法改变座位。

第七章作业答案

1. 设 ,,,,10n f f f 表示斐波那契序列。通过用小的n 值为下列每一个表达式赋值，猜测一般公式，然后用数学归纳法和斐波那契递归证明之。（c ）n n f f f f )1(210-+-+-

（d ）2

2120n f f f +++

解 (c) 对于小的n 值，列出n f 和

∑=-n

k k k f 0

)1(的值如下。

n 0 1 2 3 4 5 6 7 8

n f 0 1 1 2 3 5 8 13 21

∑=-n

k k k f 0

)1(

0 1- 0 2- 1 4- 4 9- 12

猜测：

???≥--==--=∑1

1)1(00)1(10

n f n f n n

k k k

若若

当0=n 时，00=f ，结论成立。

当1=n 时，11010--=-=-f f f ，结论成立。设1≥n 且

1)1()1(10

--=--=∑n n n

k k k f f ，则

110

1111

)1(1)1()1()1()

1(++=-+++=-+--=-+-=

-∑∑n n n

k n n n n k k n k k k

f f f f f

1)1(1)()1(1111--=---=+-++n n n n n f f f (d)

对于小的n 值，列出n f 和∑=n

k k f 0

2的值如下。

0 1 2 3 4 5 6 7 8

n f 0 1 1 2 3 5 8 13 21

∑=n

k k f 0

2 0

1 2 6 15 40 104 273 714

猜测：12

2120+=+++n n n f f f f f

当0=n 时，10200f f f ==，结论成立。

设122120+=+++n n n f f f f f ，则

21112112122120)(+++++++=+=+=++++n n n n n n n n n n f f f f f f f f f f f f

14. 求解初始值00=h ，11=h ，12=h 和23=h 的递推关系43218465----+--=n n n n n h h h h h ，（4≥n ）。解特征方程为084652

=-++-x x x x 。

因为08)1(4)1(6)1(5)1(234=--?+-?+-?--，所以1-是该方程的一个根。

88121266846522334234--++--+=-++-x x x x x x x x x x x

)1)(8126()1(8)1(12)1(6)1(2323+-+-=+-+++-+=x x x x x x x x x x x

)1()2(3+-=x x

因此，一般解为

n n n n n c n c n c c h )1(22242321-+++=

（0=n ） 041=+c c

（1=n ） 12224321=-++c c c c （2=n ） 116844321=+++c c c c （3=n ）

2722484321=-++c c c c

解该方程组得到 2781=

c 7272=c 2413-=c 27

4-=c 因此，

n n n n n n n h )1(2222782

241727278-?-?-?+?=

18. 求解非齐次递推关系

n n n h h 2341?+=- （1≥n ）

10=h

解对应齐次递推关系的特征方程为04=-x ，它的特征根为4。设该非齐次递推关系的特解为n p 2，则n n n p p 232421?+=-，因而32+=p p ，因此3-=p 。该非齐次递推关系的一般解为n n n c h 234?-=。

令0=n ，得13=-c ，解得4=c 。因此，n n n h 2341?-=+。 26. 求解非齐次递推关系

n n n h h 441+=- （1≥n ）

30=h

解法一对应齐次递推关系的特征方程为04=-x ，它的特征根为4。设该非齐次递推关系的特解为n pn 4，则n n n n p pn 44)1(441+?-?=-，解得1=p 。该非齐次递推关系的一般解为n c h n n n 44+=。令0=n ，得3=c 。因此，n n n h 4)3(?+=。解法二该序列的生成函数∑∞

)(n n n x h x g 。

∑∑∑∞

=∞

=+∞

=-=-00

104)41()()41(n n n n n

n n n

n x h x h x h x x g x

∑∑∑∞

=∞

=-∞

=--+=-+=11101

10)4(4n n n n n n n

n n

n x h h h x h x h h

x x x h n n n n n

n n n

n 411

2424340

0-+

=+=+=+=∑∑∑∞

=∞

)41(141241411

2)(x x x x x g -+-=--+

∑∑∑∞

=∞

=+=

++=0

4)3(4)1(42n n n n n

n n n

n x n x n x

因此，n n n h 4)3(?+=。

30. 确定苹果、桔子、香蕉和梨的袋装水果的袋数n h 的生成函数，其中各袋要有偶数个苹果，最多两个桔子，3的倍数个香蕉，最多一个梨。然后从该生成函数求出n h 的公式。解生成函数

)1)()(1)(()(0

2x x x x x x g n n n n +++=∑∑∞

=∞

322)1(1)

1)(1()1)(1(x x x x x x -=

--+++=

∑

∞

=+=

)1(n n x n 因此，1+=n h n 。

32. 令 ,,,,,210n h h h h 是由???

??=2n h n 定义的序列（0≥n ）

。确定该序列的生成函数。解

x n n -=

∑∞

=110 两边求导数得到

01)

1(1x nx n n -=

∑∞

两边再求导数得到

2)1(2

)1(x x n n n n -=-∑∞

两边乘2

x 得到

)1(2)1(x x x n n n n -=-∑∞

= 因此，该序列的生成函数

∑∑∑∞

=∞=∞

=-=-=???? ??==00

0)1(2)1(2)(n n n n n n

n x x x n n x n x h x g 32. 令 ,,,,,210n h h h h 是由????

??=2n h n 定义的序列（0≥n ）

。确定该序列的指数生成函数。

解该序列的指数生成函数

∑∑∑∞=∞=∞

=???? ??=???? ??==200

)

(!2!2!)(n n n n n n

n e n x n n x n n x h x g

2!2!

21!)2(21!!)2(!2!2020222x

n n n n n n n n e x n x x n x n x n n x n ===-=-=∑∑∑∑∞=∞=+∞=∞

= 41. 确定所有的数字至少是4的n 位数的个数，其中4和6每个都出现偶数次，5和7每个至少出现1次，但对于数字8和9则没有限制。

解设n h 为满足条件的n 位数的个数，序列 ,,,210h h h 的指数生成函数是

222

32242)

()!

21()!3!2()!4!21()( +++++++++=x x x x x x x x g

4)12)(2()1(4)(2222222x x x x x x

x x x e e e e e e e e e +-++=-+=--

12343223456+-+-+-=x x x x x x e e e e e e

41!21!243!3!443!521!6410

00000+-+-+-=∑∑∑∑∑∑∞=∞=∞=∞=∞=∞=n n n n n n n

n n n n n n n n n n n x n x n x n x n x n x

∑

∞

=-?+?-?+?-=1

!42233443526n n

n n n n n n x

因此，??

??≥-?+?-?+?-==1

23344352600

n n h n n n n n n 若若

第八章作业答案

1. 设在圆上选择n 2个（等间隔的）点。证明将这些点成对连接起来所得到的n 条线段不相交的方法数等于第n 个Catalan 数n C 。

证明设n h 为将圆上的n 2个点成对连接起来得到n 条不相交线段的方法数。我们证明序列 ,,,210h h h 与Catalan 数序列 ,,,210C C C 满足同样的递推关系和初始条件。设圆上的n 2个点顺时针依次排列为12210,,,,-n a a a a ，若连接线段k a a 0，则其左边和右边的点不能相互连接，那样会与k a a 0相交。k a a 0左边的点的数目和它右边的点的数目都应当是偶数，即k 是奇数。若k a a 0左边的点的数目是i 2，则k a a 0右边的点的

数目就是)1(2i n --。随着k 从1变到12-n ，i 从0变到1-n 。因此，序列 ,,,210h h h 满足递推关系

012110h h h h h h h n n n n ---+++=

令1-=n n C g ，则???

??--=1221n n n g n 。由定理7.6.1知道序列 ,,,321g g g 满足递推关系 112211g g g g g g g n n n n ---+++=

因此，

01211011211C C C C C C g g g g g g g C n n n n n n n n ----++++=+++==

又有001C h ==，序列 ,,,210h h h 与Catalan 数序列 ,,,210C C C 满足同样的递推关系和初始条件。

8. 求前n 个正整数的五次幂的和。

解计算序列 ,,,2,1,05555n 的差分表如下。

0 1 32 243 1024 3125 …

1 31 211 781 2101 … 30 180 570 1320 … 150 390 750 … 240 360 … 120 … 其差分表的第0条对角线为

0，1，30，150，240，120，0，0，…

因此

???? ??++???? ??++???? ??++???? ??++???? ??++???? ??+=∑=61120512404115031302111100

n n n n n n k n

k 12. 证明第二类Stirling 数满足关系 (a ) 1)1,(=n S ，)1(≥n (b ) 12)2,(1-=-n n S ，)2(≥n (c ) ???

? ??=-2)1,(n n n S ，)1(≥n

(d ) ???

? ??+????

??=-433)2,(n n n n S ，)2(≥n

证明 (a ) 设1≥n ，因为将个物体放入1个盒子中，只有一种方法，所以1)1,(=n S 。

(b ) 设2≥n ，A 是n -元集，则A 的非空真子集的个数为22-n

。任取A 的非空真子集B ，将B 中元素放入一个盒子，而将其他元素放入另一个盒子，就得到一种将A 中元素放入两个非空盒子的方法。显然，B 和它的补集B A -对应同一种方法，即每种方法都对应A 的两个子集。因此，122/)22()2,(1-=-=-n n n S 。

(c ) 设1≥n 。若1=n ，则???

??==-20)1,(n n n S 。下面考虑2≥n 的情况。将n 个物体放入

1-n 个非空盒子中，必然有一个盒子中有两个物体，而其余盒子中只有一个物体。设A

是n -元集，任取A 的2-组合B ，将B 中元素放入一个盒子，将其余元素各放进一个盒子，就得到将n 个物体放入1-n 个非空盒子中的方法。因此，可在A 的2-组合和将n 个物体放入1-n 个非空盒子中的方法之间建立一一对应。所以，???

??=-2)1,(n n n S 。

(d ) 设2≥n 。若2=n ，???

? ??+????

??==-4330)2,(n n n n S 。下面考虑3≥n 的情况。将n 个物体放入2-n 个非空盒子中，有两种可能。一种情况是，有一个盒子中放入3个物体，其余盒子中各放入一个物体，这种情况发生的次数是???

? ??3n 。另一种情况是，有两个盒子中各放入2个物体，其余盒子中各放入一个物体。从这n 个物体中任取出四个，设它们是

d c b a ,,,，a 可与d c b ,,之一在一个盒子中。因此，这种情况发生的次数是????

??43n 。所以，

???

??+???? ??=-433)2,(n n n n S 。

13. 令X 是p -元集并令Y 是k -元集。证明，把X 映射到Y 上的函数Y X f →:的个数等于

),(),(!#k p S k p S k =

证明设},,,{21k b b b Y =。将k b b b ,,,21 看作k 个不同盒子，若i b x f =)(，则把

X 中元素x 放入盒子i b ，这在X 映射到Y 上的函数和将X 中元素放入k 个不同非空

盒子的方法之间建立了一一对应。因此，把X 映射到Y 上的函数Y X f →:的个数等

于),(),(!#k p S k p S k =。

(完整word版)组合数学课后答案

习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。

任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。

一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。

排列组合知识点总结+典型例题及答案解析

排列组合知识点总结+典型例题及答案解析一．基本原理 1．加法原理：做一件事有n 类办法，则完成这件事的方法数等于各类方法数相加。 2．乘法原理：做一件事分n 步完成，则完成这件事的方法数等于各步方法数相乘。注：做一件事时，元素或位置允许重复使用，求方法数时常用基本原理求解。二．排列：从n 个不同元素中，任取m （m ≤n ）个元素，按照一定的顺序排成一 .m n m n A 有排列的个数记为个元素的一个排列，所个不同元素中取出列，叫做从 1.公式：1.()()()()! ! 121m n n m n n n n A m n -=+---=…… 2. 规定：0!1= (1)!(1)!,(1)!(1)!n n n n n n =?-+?=+ (2) ![(1)1]!(1)!!(1)!!n n n n n n n n n ?=+-?=+?-=+-； (3) 111111 (1)!(1)!(1)!(1)!!(1)! n n n n n n n n n +-+==-=- +++++ 三．组合：从n 个不同元素中任取m （m ≤n ）个元素并组成一组，叫做从n 个不同的m 元素中任取 m 个元素的组合数，记作 Cn 。 1. 公式： ()()()C A A n n n m m n m n m n m n m m m ==--+= -11……!! !! 10 =n C 规定：组合数性质： .2 n n n n n m n m n m n m n n m n C C C C C C C C 21011 =+++=+=+--…… ，， ①；②；③；④ 111 12111212211 r r r r r r r r r r r r r r r r r r n n r r r n n r r n n n C C C C C C C C C C C C C C C +++++-+++-++-++++ +=+++ +=++ +=注：若1 2 m m 1212m =m m +m n n n C C ==则或四．处理排列组合应用题 1.①明确要完成的是一件什么事（审题） ②有序还是无序 ③分步还是分类。

组合数学作业答案

第二章作业答案 7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。证明用100分别除这52个整数，得到的余数必为0, 1,…, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，…，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a 和b 。若a 和b 被100除余数相同，则b a -能被100整除。若a 和b 被100除余数之和是100，则b a +能被100整除。 11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。证明设从第一天到第i 天她共学习了i a 小时。因为她每天至少学习1小时，所以 3721,,,a a a 和13,,13,133721+++a a a 都是严格单调递增序列。因为总的学习时间不超过 60 小时，所以6037≤a ，731337≤+a 。3721,,,a a a , 13,,13,133721+++a a a 是1和73之间的74个整数，由鸽巢原理知道，它们中存在相同的整数，有i a 和13+j a 使得13+=j i a a ，13=-j i a a ，从第1+j 天到第i 天她恰好学习了13小时。 14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？解由加强形式的鸽巢原理知道，如果从袋子中取出451)112(4=+-?个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。 17. 证明：在一群1>n 个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。证明因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到1-n 的整数。若有两个人的熟人的数目分别是0和1-n ，则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n 个人的熟人的数目是1-n 个整数之一，必有两个人有相同数目的熟人。第三章作业答案 6. 有多少使下列性质同时成立的大于5400的整数？ (a) 各位数字互异。 (b) 数字2和7不出现。解因为只能出现数字0, 1, 3, 4, 5, 6, 8, 9，所以整数的位数至多为8。

组合数学课后答案

作业习题答案习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n 个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：方法一：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数 = 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。方法二：对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.9将一个矩形分成(m +1)行112m m +?? + ??? 列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。证明：（1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。（2）每列中两个单元格的不同位置组合有12m +?? ??? 种，这样一列中两个同色单元格的位置组合共有 12m m +?? ??? 种情况（3）现在有112m m +?? + ??? 列，根据鸽巢原理，必有两列相同。证明结论成立。 2.11证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。证明：

高中数学排列组合典型例题精讲

概念形成 1、元素：我们把问题中被取的对象叫做元素 2、排列：从n 个不同元素中，任取m （m n ≤）个元素（这里的被取元素各不相同）按照一定的顺．．．．序．排成一列，叫做从n 个不同元素中取出m 个元素的一个排列．．．．。说明：（1）排列的定义包括两个方面：①取出元素，②按一定的顺序排列（与位置有关）（2）两个排列相同的条件：①元素完全相同，②元素的排列顺序也相同合作探究二排列数的定义及公式 3、排列数：从n 个不同元素中，任取m （m n ≤）个元素的所有排列的个数叫做从n 个元素中取出 m 元素的排列数，用符号m n A 表示议一议：“排列”和“排列数”有什么区别和联系？ 4、排列数公式推导探究：从n 个不同元素中取出2个元素的排列数2n A 是多少？3n A 呢？m A n 呢？ )1()2)(1(+-?--=m n n n n A m n （,,m n N m n *∈≤）说明：公式特征：（1）第一个因数是n ，后面每一个因数比它前面一个少1，最后一个因数是1n m -+，共有m 个因数；（2）,,m n N m n *∈≤ 即学即练: 1.计算 (1）410A ； (2）25A ；(3)3355A A ÷ 2.已知101095m A =???，那么m = 3．,k N +∈且40,k ≤则(50)(51)(52)(79)k k k k ----用排列数符号表示为( ) A ．5079k k A -- B ．2979k A - C ．3079k A - D ．3050k A - 例1．计算从c b a ,,这三个元素中，取出3个元素的排列数，并写出所有的排列。 5 、全排列：n 个不同元素全部取出的一个排列，叫做n 个不同元素的全排列。此时在排列数公式中， m = n 全排列数：(1)(2)21!n n A n n n n =--?=（叫做n 的阶乘）. 即学即练:口答（用阶乘表示）：（1）334A （2）44A （3）)!1(-?n n 排列数公式的另一种形式： )! (!m n n A m n -= 另外，我们规定 0! =1 .

完整版排列组合练习题及答案

排列组合》一、排列与组合 1. 从9 人中选派2 人参加某一活动，有多少种不同选法？ 2. 从9人中选派2人参加文艺活动，1人下乡演出，1人在本地演出，有多少种不同选派方法？ 3. 现从男、女8名学生干部中选出2名男同学和1 名女同学分别参加全校“资源”、“生态” 和“环保”三个夏令营活动，已知共有90 种不同的方案，那么男、女同学的人数是 A.男同学2人，女同学6人 B.男同学3人，女同学5人 C. 男同学5人，女同学3人 D. 男同学6人，女同学2人 4. 一条铁路原有m个车站，为了适应客运需要新增加n个车站（n>1），则客运车票增加了58 种（从甲站到乙站与乙站到甲站需要两种不同车票），那么原有的车站有 A.12 个 B.13 个 C.14 个 D.15 个 5．用0，1 ，2，3，4，5 这六个数字，（1 ）可以组成多少个数字不重复的三位数？（2）可以组成多少个数字允许重复的三位数？（3）可以组成多少个数字不允许重复的三位数的奇数？（4）可以组成多少个数字不重复的小于1000 的自然数？（5）可以组成多少个大于3000，小于5421 的数字不重复的四位数？二、注意附加条件 1.6 人排成一列（1 ）甲乙必须站两端，有多少种不同排法？（2）甲乙必须站两端，丙站中间，有多少种不同排法？ 2. 由1 、2、3、4、5、6 六个数字可组成多少个无重复数字且是6 的倍数的五位数？ 3. 由数字1 ，2，3，4，5，6，7 所组成的没有重复数字的四位数，按从小到大的顺序排列起来，第379 个数是 A.3761 B.4175 C.5132 D.6157 4. 设有编号为1、2、3、4、5 的五个茶杯和编号为1、2、3、4、5的五个杯盖，将五个杯盖盖在

组合数学课后标准答案

————————————————————————————————作者：————————————————————————————————日期：

任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。

一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。

排列组合典型例题

排列组合典型例题排列组合问题联系实际生动有趣，但题型多样，思路灵活，因此解决排列组合问题，首先要认真审题，弄清楚是排列问题、组合问题还是排列与组合综合问题；其次要抓住问题的本质特征，采用合理恰当的方法来处理。教学目标 1.进一步理解和应用分步计数原理和分类计数原理。 2.掌握解决排列组合问题的常用策略;能运用解题策略解决简单的综合应用题。提高学生解决问题分析问题的能力 3.学会应用数学思想和方法解决排列组合问题. 复习巩固 1.分类计数原理(加法原理) 完成一件事，有n 类办法，在第1类办法中有1m 种不同的方法，在第2类办法中有2m 种不同的方法，…，在第n 类办法中有n m 种不同的方法，那么完成这件事共有： 12n N m m m =+++ 种不同的方法． 2.分步计数原理（乘法原理）完成一件事，需要分成n 个步骤，做第1步有1m 种不同的方法，做第2步有2m 种不同的方法，…，做第n 步有n m 种不同的方法，那么完成这件事共有： 12n N m m m =??? 种不同的方法． 3.分类计数原理分步计数原理区别分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件．解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。 3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素. 4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略一.特殊元素和特殊位置优先策略例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置.

组合数学题目及标准答案

组合数学例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态? 解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!＝40320。例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。证明n 偶数。证：由于每一次握手均使握手的两人各增加一次与他人握手的次数，因此n 位客人与他人握手次数的总和 nd 是偶数 — 握手次数的2倍。根据奇偶性质，已知d 是奇数，那么n 必定是偶数。例４从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。证设n +1个数是a 1, a 2, ···, an +1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r 1, r 2,, ···, rn +1。这n +1个数仍在[1 , 2n ]中，且都是奇数。而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。若ai ＞aj ，则ai 是aj 的倍数。例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k h ，使得 ah+1+…+ ak= 39 证令Sj= ，j =1 , 2 , …,100。显然 ∑=j i i a 1 ∑=h i i a 1

高中数学排列组合经典题型全面总结版

高中数学排列与组合（一）典型分类讲解一.特殊元素和特殊位置优先策略例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排, 先排末位共有1 3C 然后排首位共有1 4C 最后排其它位置共有 34A 由分步计数原理得1 1 3 434 288C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？二.相邻元素捆绑策略例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有 522522480A A A =种不同的排法练习题:某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为 20 三.不相邻问题插空策略例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种？解:分两步进行第一步排2个相声和3个独唱共有55A 种，第二步将4舞蹈插入第一步排好的6个元素中间包含首尾两个空位共有种 46 A 不同的方法,由分步计数原理,节目的不同顺序共有54 56A A 种练习题：某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为 30 四.定序问题倍缩空位插入策略例4. 7人排队,其中甲乙丙3人顺序一定共有多少不同的排法解:(倍缩法)对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进行排列,然后用总排列数除以这几个元素之间的全排列数,则共有不同排法种数是： 73 73/A A (空位法)设想有7把椅子让除甲乙丙以外的四人就坐共有 47 A 种方法，其余的三个位置甲乙丙共有 1种坐法，则共有4 7A 种方法。思考:可以先让甲乙丙就坐吗? （插入法)先排甲乙丙三个人,共有1种排法,再把其余4四人依次插入共有方法练习题:10人身高各不相等,排成前后排，每排5人,要求从左至右身高逐渐增加，共有多少排法？ 5 10C 五.重排问题求幂策略例5.把6名实习生分配到7个车间实习,共有多少种不同的分法解:完成此事共分六步:把第一名实习生分配到车间有 7 种分法.把第二名实习生分配到车间也有7种分依此类推,由分步计数原理共有6 7种不同的排法练习题： 1．某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插法的种数为 42 4 4 3 允许重复的排列问题的特点是以元素为研究对象，元素不受位置的约束，可以逐一安排各个元素的位置，一般地n 不同的元素没有限制地安排在m 个位置上的排列数为n m 种

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

第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2 …a 1 是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1) 表示。 a n 可以有两种情况： 1）不管上述序列中是否有2，因为a n 的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选；故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n 1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2）将（1）得到的h(n)=(2n+4n)/2代入（2），可得 n+4n)/2-2f(n), 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个；所以 f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能；依此类推，有 17

高中数学排列组合题型总结与易错点提示25587汇编

排列组合复习巩固 1.分类计数原理(加法原理) 完成一件事，有n 类办法，在第1类办法中有1 m 种不同的方法，在第2类办法中有2 m 种不同的方法，…，在第n 类办法中有n m 种不同的方法，那么完成这件事共有：12n N m m m =+++种不同的方法． 2.分步计数原理（乘法原理）完成一件事，需要分成n 个步骤，做第1步有1 m 种不同的方法，做第2步有2m 种不同的方法，…，做第n 步有n m 种不同的方法，那么完成这件事共有：12n N m m m =???种不同的方法． 3.分类计数原理分步计数原理区别分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件．一.特殊元素和特殊位置优先策略例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置. 先排末位共有13 C C 1 4 A 3 4 C 1 3 然后排首位共有14 C 最后排其它位置共有34 A 由分步计数原理得113434 288C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花

不种在中间，也不种在两端的花盆里，问有多少不同的种法？二.相邻元素捆绑策略例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有5225 2 2 480A A A 种不同的排法乙甲丁丙练习题:某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为 20 三.不相邻问题插空策略例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种？解:分两步进行第一步排2个相声和3个独唱共有55 A 种，第二步将4舞蹈插入第一步排好的6个元素中间包含首尾两个空位共有种46 A 不同的方法,由分步计数原理,节目的不同顺序共有5456 A A 种练习题：某班新年联欢会原定的5个节目已排成节目单，要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素一起作排列 ,同时要注意合并元素内部也必须排列. 元素相离问题可先把没有位置要求的元素进行排队再把不相邻元素插入中间和两端

高中数学排列组合中的典型例题与分析(三)

排列与组合的八大典型错误、 24种解题技巧三大模型一、知识点归纳二、基本题型讲解三、排列组合解题备忘录 1.分类讨论的思想 2.等价转化的思想 3.容斥原理与计数 4.模型构造思想四、排列组合中的8大典型错误 1．没有理解两个基本原理出错 2.判断不出是排列还是组合出错 3.重复计算出错 4.遗漏计算出错 5.忽视题设条件出错 6.未考虑特殊情况出错 7．题意的理解偏差出错 8.解题策略的选择不当出错五、排列组合24种解题技巧 1．排序问题相邻问题捆绑法相离问题插空排定序问题缩倍法（插空法）定位问题优先法多排问题单排法圆排问题单排法可重复的排列求幂法全错位排列问题公式法 2．分组分配问题平均分堆问题去除重复法（平均分配问题）相同物品分配的隔板法全员分配问题分组法有序分配问题逐分法 3．排列组合中的解题技巧至多至少间接法染色问题合并单元格法交叉问题容斥原理法构造递推数列法六．排列组合中的基本模型分组模型（分堆模型）错排模型染色问题

七．排列组合问题经典题型与通用方法（一）排序问题 1.相邻问题捆绑法:题目中规定相邻的几个元素捆绑成一个组，当作一个大元素参与排列.例1.,,,,A B C D E 五人并排站成一排，如果,A B 必须相邻且B 在A 的右边，则不同的排法有（）A、60种 B、48种 C、36种 D、24种解析：把,A B 视为一人，且B 固定在A 的右边，则本题相当于4人的全排列，4 424A =种，答案：D . 2.相离问题插空排:元素相离（即不相邻）问题，可先把无位置要求的几个元素全排列，再把规定的相离的几个元素插入上述几个元素的空位和两端. 例2.七人并排站成一行，如果甲乙两个必须不相邻，那么不同的排法种数是（）A、1440种B、3600种C、4820种D、4800种解析：除甲乙外，其余5个排列数为5 5A 种，再用甲乙去插6个空位有2 6A 种，不同的排法种数是5 2 563600A A =种，选B . 3.定序问题缩倍法:在排列问题中限制某几个元素必须保持一定的顺序，可用缩小倍数的方法. 例3.A,B,C,D,E 五人并排站成一排，如果B 必须站在A 的右边（,A B 可以不相邻）那么不同的排法有（）A、24种B、60种C、90种D、120种解析：B 在A 的右边与B 在A 的左边排法数相同，所以题设的排法只是5个元素全排列数的一半，即 5 51602 A =种，选 B .11.定位问题优先法：某个或几个元素要排在指定位置，可先排这个或几个元素；再排其它的元素。例11.现有1名老师和4名获奖同学排成一排照相留念，若老师不站两端则有不同的排法有多少种？解析：老师在中间三个位置上选一个有1 3A 种，4名同学在其余4个位置上有4 4A 种方法；所以共有1 4 3472A A =种。 12.多排问题单排法:把元素排成几排的问题可归结为一排考虑，再分段处理。例12.（1）6个不同的元素排成前后两排，每排3个元素，那么不同的排法种数是（）A、36种B、120种C、720种D、1440种（2）8个不同的元素排成前后两排，每排4个元素，其中某2个元素要排在前排，某1个元素排在后排，有多少种不同排法？解析：（1）前后两排可看成一排的两段，因此本题可看成6个不同的元素排成一排，共 66720A =种，选C . （2）解析：看成一排，某2个元素在前半段四个位置中选排2个，有2 4A 种，某1个元素排在后半段的四个位置中选一个有1 4A 种，其余5个元素任排5个位置上有5 5A 种，故共有1 2 5 4455760A A A =种排法. 16.圆排问题单排法:把n 个不同元素放在圆周n 个无编号位置上的排列，顺序（例如按顺时钟）不同的排法才算不同的排列，而顺序相同（即旋转一下就可以重合）的排法认为是相同的，它与普通排列的区别在于只计顺序而无首位、末位之分，下列n 个普通排列：

组合数学作业答案1-2章2016

组合数学作业第一章引言 Page 13, ex3,4,7,30 ex3. 想象一座有64个囚室组成的监狱，这些囚室被排列成8 8棋盘。所有相邻的囚室间都有门。某角落处意见囚室例的囚犯被告知，如果他能够经过其它每一个囚室正好一次之后，达到对角线上相对的另一间囚室，那么他就可以获释。他能获得自由吗？解：不能获得自由。方法一：对64个囚室用黑白两种颜色染色，使得横和竖方向相邻的囚室颜色不同。则对角线上两个囚室颜色为同黑或同白。总共偶数个囚室，若能遍历且不重复，则必然是黑出发白结束，矛盾。方法二：64个囚室，若要经过每个囚室正好一次，需要走63步，即奇数步。不妨假设该囚犯在第1行第1列，那么到第8行第8列，横着的方向需要走奇数步，竖着的方向需要走奇数步，即总共需要偶数步。所以不能恰好经过每个囚室一次到达对角线上的囚室。 ex4. (a) 设f(n)是用多米诺牌(2-牌)对2×n棋盘作完美覆盖的个数。估计一下f(1),f(2),f(3),f(4)和f(5). 试寻找(或证明)这个计数函数f满足的简单关系。利用这个关系计算f(12)。 (b) 设g(n)是用多米诺牌(2-牌)对3×n棋盘作完美覆盖的个数。估计g(1),g(2),…,g(6). 解：(a) f(1)=1, f(2)=2, f(3)=3, f(n+2)=f(n+1)+f(n) f(4)=f(3)+f(2)=5, f(5)=f(4)+f(3)=8 f(6)=f(5)+f(4)=13 f(7)=f(6)+f(5)=21 f(8)=f(7)+f(6)=34 f(9)=f(8)+f(7)=55 f(10)=f(9)+f(8)=89 f(11)=f(10)+f(9)=144 f(12)=f(11)+f(10)=233 (b) g(1)=0, g(2)=3, g(3)=0, g(4)=9+2=11, g(n+4)=4g(n+2)-g(n), g(5)=0, g(6)=41. ex7. 设a和b是正整数，且a是b的因子。证明m×n棋盘有a×b的完美覆盖当且仅当a 既是m又是n的因子，而b是m或n的因子。(提示: 把a×b牌分割成a个1×b牌。) 解：充分性。当a既是m又是n的因子，而b是m或n的因子，则m×n棋盘有a×b的平凡完美覆盖。必要性。假设m×n棋盘有a×b牌的完美覆盖。则m×n棋盘必有b牌的完美覆盖。根据书中的定理，b是m的因子或n的因子。下面证明a既是m的因子又是n的因子。方法一: 因为a是b的因子，所以a×b牌可以分割成b/a个a×a牌。m×n棋盘有a×a的完美覆盖，则必然有a×a牌的完美覆盖。而a×a牌是正方形的，所以只有唯一的一种平凡覆盖方式。从而m是a的倍数，n也是a的倍数。方法二: 因为a是b的因子，不妨设b=ka。由m×n棋盘有a×b牌的完美覆盖，可任取一个完美覆盖。设第一行的n个方格由p个a×b牌和q个b×a牌盖住，则有n=pb+qa=(pk+q)a，所以n是a的倍数。同理，m也是a的倍数。

组合数学课后答案

习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。

2.2任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。

2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.5一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。

排列组合计算公式及经典例题汇总

排列组合公式/排列组合计算公式排列A------和顺序有关组合 C -------不牵涉到顺序的问题排列分顺序,组合不分例如把5本不同的书分给3个人,有几种分法. "排列" 把5本书分给3个人,有几种分法"组合" 1．排列及计算公式从n个不同元素中，任取m(m≤n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号A(n,m)表示. A(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!(规定0!=1). 2．组合及计算公式从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n 个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号

c(n,m) 表示. c(n,m)=A(n,m)/m!=n!/((n-m)!*m!)；c(n,m)=c(n,n-m); 3．其他排列与组合公式从n个元素中取出r个元素的循环排列数＝A(n,r)/r=n!/r(n-r)!. n个元素被分成k类，每类的个数分别是n1,n2,...nk这n个元素的全排列数为 n!/(n1!*n2!*...*nk!). k类元素,每类的个数无限,从中取出m个元素的组合数为 c(m+k-1,m). 排列（Anm(n为下标，m为上标)） Anm=n×（n-1）....（n-m+1）；Anm=n！/（n-m）！（注：！是阶乘符号）；Ann（两个n分别为上标和下标）=n！；0！=1；An1（n为下标1为上标）=n

组合数学6章作业答案

第6章容斥原理及应用 6.7 练习题 3、求出从1到10000既不是完全平方数也不是完全立方数的整数个数。解：∵100001002=,9261213=,10648223= ∴从1到10000，共有100个平方数，21个立方数又∵409646=，1562556= ∴从1到10000，共有4个6次方数，也就是共有4个数既是平方数又是立方数计算：10000-100-21+4=9883 ∴从1到10000既不是完全平方数也不是完全立方数的整数有9883个 □ 4、确定多重集{}d c b a S ????=5,4,34，的12-组合的个数。解：设T ：{}d c b a S ?∞?∞?∞?∞=,,,*的所有12-组合 1A ：a 的个数大于4的12-组合 2A ：b 的个数大于3的12-组合 3A ：c 的个数大于4的12-组合 4A ：d 的个数大于5的12-组合要求的是： 4321A A A A ??? = T )(4321A A A A +++- )(434232413121A A A A A A A A A A A A ?+?+?+?+?+?+ )(432431421321A A A A A A A A A A A A ??+??+??+??- )(4321A A A A ???+ T =??? ? ??-+121412=455 1A =???? ??-+7147=120 2A =???? ??-+8148=165 3A =???? ??-+7147=120 4A =??? ? ??-+6146=84

21A A ?=???? ??-+3143=20 31A A ?=???? ??-+2142=10 41A A ?=???? ??-+1141=4 32A A ?=???? ??-+3143=20 42A A ?=???? ??-+2142=10 43A A ?=???? ??-+1141=4 321A A A ??=421A A A ??=431A A A ??=432A A A ??=4321A A A A ???=0 455-（120+165+120+84）+（20+10+4+20+10+4）=34 ∴多重集{}d c b a S ????=5,4,34，的12-组合的个数是34 □ 9、确定方程 204321=+++x x x x 满足 611≤≤x ，702≤≤x ，843≤≤x ，624≤≤x 的整数解的个数。解：设 116x y -=， 227x y -=， 338x y -=， 446x y -= 则原方程等价于确定方程 74321=+++y y y y 满足 501≤≤y ， 702≤≤y ， 403≤≤y ， 404≤≤y 的整数解的个数。设S ：74321=+++y y y y 的所有非负整数解的集合 1A ：74321=+++y y y y 的所有满足61≥y 的非负整数解的集合 2A ：74321=+++y y y y 的所有满足82≥y 的非负整数解的集合 3A ：74321=+++y y y y 的所有满足53≥y 的非负整数解的集合 4A ：74321=+++y y y y 的所有满足54≥y 的非负整数解的集合若j i ≠，则?=?j i A A ,那么要求的是：

组合数学作业答案解析

(完整word版)组合数学课后答案

排列组合知识点总结+典型例题及答案解析

组合数学作业答案

组合数学课后答案

高中数学排列组合典型例题精讲

完整版排列组合练习题及答案

组合数学课后标准答案

排列组合典型例题

组合数学题目及标准答案

高中数学排列组合经典题型全面总结版

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

高中数学排列组合题型总结与易错点提示25587汇编

高中数学排列组合中的典型例题与分析(三)

组合数学作业答案1-2章2016

组合数学 课后答案

排列组合计算公式及经典例题汇总

组合数学6章作业答案

最新排列组合知识点汇总及典型例题(全)

组合数学课后答案