当前位置：文档库 › 组合数学(西安电子科技大学(第二版))习题4答案

组合数学(西安电子科技大学(第二版))习题4答案

习题四（容斥原理）

1．试求不超过200的正整数中素数的个数。

解：因为2215225,13169==，所以不超过200的合数必是2,3,5,7,11,13的倍数，

而且其因子又不可能都超过13。

设i A 为数i 不超过200的倍数集，2,3,5,7,11,13i =，则

22001002A ??==????，3200663A ??==????，5200405A ??==????，7200287A ??

==????， 112001811A ??==????，132001513A ??==????，232003323A A ??==?????

， 252002025A A ??==?????，272001427A A ??==?????，2112009211A A ??

==?????， 2132007213A A ??==?????，352001335A A ??==?????

，37200937A A ??==?????， 3112006311A A ??==?????，3132005313A A ??==?????，57200557A A ??==?????， 5112003511A A ??==?????，5132003513A A ??==?????，7112002711A A ??==?????， 7132002713A A ??==?????，111320011113A A ??==?????，2352006235A A A ??==??????， 2372004237A A A ??==??????，231120032311A A A ??==??????，231320022313A A A ??

==?????? 2572002257A A A ??==??????，251120012511A A A ??==??????，251320012513A A A ??

==??????， 271120012711A A A ??==??????，271320012713A A A ??==??????

， 21113200021113A A A ??==??????，3572001357A A A ??==??????

，351120013511A A A ??==??????

351320013513A A A ??==??????，371120003711A A A ??

==??????

，…， 235720002357A A A A ??==???????，…，23571113200023571113A A A A A A ??

==?????????

，所以 2357

13200(1006640281815)(3320149713965533221)

(6432211110111i i j i j k i j k l

i k

i j k

i j k l m

i j k l m n

i j k l m

j k l m n

A A A A A A S A A A A A A A A A A A A A A A A A A A A A <<<<<<<<<<<<<<<=-+-+

+=-++++++++++++++++++++-+++++++++++++∑∑∑∑∑

∑

0)00041

+-+=

但这41个数未包括2,3,5,7,11,13本身，却将非素数1包含其中，故所求的素数个数为：416146+-=

2．问由1到2000的整数中：

（1）至少能被2，3，5之一整除的数有多少个？

（2）至少能被2，3，5中2个数同时整除的数有多少个？（3）能且只能被2，3，5中1个数整除的数有多少个？解：设i A 为1到2000的整数中能被i 整除的数的集合，2,3,5i =，

则2200010002A ??==????，320006663A ??==????，520004005A ??

==????， 23200033323A A ??==?????，25200020025A A ??==?????，35200013335A A ??

==?????， 235200066235A A A ??

==??????

，（1）即求235A A A ++，根据容斥原理有：

2352352325352

()1000666400(333200133)661466

A A A A A A A A A A A A A A A

++=++-+++=++-+++=

（2）即求232535A A A A A A ++，根据容斥原理有：

23253

2325352352352352

()333200133266534

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

（3）即求[1]N ，根据Jordan 公式有：

1112233

235232535235[1]2()310006664002(333200133)366932

N q C q C q A A A A A A A A A A A A =-+=++-?+++?=++-?+++?=

3．求从1到500的整数中能被3和5整除但不能被7整除的数的个数。解：设i A 为1到500的整数中能被i 整除的数的集合，3,5,7i =，

则35001663A ??==????，55001005A ??==????，7500717A ??

==????， 355003335A A ??==?????，375002337A A ??==?????，575001457A A ??==?????， 3575004357A A A ??==??????

，满足条件的整数个数为：357A A A ，根据容斥原理有： 35735

35733429

A A A A A A A A =-=-=

4．某人参加一种会议，会上有6位朋友，他和其中每一人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，与六人都相遇1次，一人也没遇见的有5次。问该人共参加几次会议？解：设S 为该人参加的所有会议组成的集合，

设i A 表示该人与第i 个朋友相遇的所有会议构成的子集，1,2,,6i = ，则 112i R A ==，1,2,,6i =

26i j R A A ==，34i j k R A A A ==，43i j k l R A A A A ==，52i j k l m R A A A A A ==，

61234561R A A A A A A ==，

则，

123456

12345

6616263646566

61215620415362128

A A A A A A C R C R C R C R C R C R +++++=-+-+-=?-?+?-?+?-=

则该人共参加会议次数为： 28533S =+=（次）。

5．n 位的四进制数中，数字1，2，3各自至少出现一次的数有多少个？解：设S 表示所有n 位四进制数构成的集合，

i A 为不出现i 的数的集合，1,2,3i =，

则1233n A A A ===，1213232n A A A A A A ===，1231A A A =，则由逐步淘汰原理，可得 123123121323123

()()43

321

n n

A A A S A A A A A A A A A A A A +=-+++++-=-+?-

6．某照相馆给n 个人分别照相后，装入每人的纸袋里，问出现以下情况有多少种可能？

（1）没有任何一个人得到自己的照片；（2）至少有一人得到自己的相片；（3）至少有两人得到自己的照片；

解：以任一种装法为元素构成的集合记为S ，则!S n =。

设i A 表示第i 个人拿到自己的照片的所有装法组成的集合。则公共数

1(1)!i R A n ==-，同理2(2)!i j R A A n ==-，……， 12()!,1,2,,k k i i i R A A A n k k n ==-=

（1）即求[0]N ，由问题的性质可知，这是一个错排问题，所以

1[0]!1(1)1!2!

!n n N D n n ??==-+-+- ???

（2）即求[1]L ，111

1[1][0]!!(1)1!2!

!n n L S N n D n n -??=-=-=-++- ???

? 方法二：

问题即：将所有可能的分配方案－没有任何一人得到自己的照片的方案，则，符合条件的方案数为：!n n D -， ? 方法三：

问题即求：

()()112121112111

1!11!2!3!

!n n n

n n n n A A A R R R n n n --??????

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

（3）问题即求：[2][0][1]L S N N =--，

11121311

11223311[2][0]

[1]

!((1))

2!!3!!

!((1)!(

2)!(

3)!

1!2!(2)!2!3!(3)!

(1)0!)

(1)!!0!

111

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

n n n n L S N N n D C C R C C R C C R C C R n n n D n n n n n n n n n n n D n n n ---=--=---+-+-=--?--?-+?----+-?-=--?--+-+-- 1

!n n n D nD -????

?=--

7．把{,,,,,,,,}a a a b b b c c c 排成相同字母互不相邻的排列，有多少种排法？

解：设S 为所有排列的组成的集合，则9!

16803!3!3!S ==，

设i A ：表示排列中有相邻i 个元素都是a 的排列集合；2,3i =；

设i B ：表示排列中有相邻i 个元素都是b 的排列集合；2,3i =；设i C ：表示排列中有相邻i 个元素都是c 的排列集合；2,3i =；则：3337!1401!3!3!A B C ===

=，3333335!

201!1!3!

A B A C B C ====， 3333!6A B C ==，（即将aaa 、bbb 或ccc 看为一个元素）

2228!7!

11201409801!1!3!3!1!3!3!

A B C ===

-=-=

（将aa 与a 看做为不同的两个元素参与排列，但在出现aaa 时就重复计算，(aa)a 、a(aa)看为两个不同的排列，因此aaa 多计算了一次）

因为22A B 为aa,bb 图象都出现的排列集合，当我们将aa 与a ，bb 与b 看作不同的两对元素进行排列时，在aa 与a 相遇而成aaa 图象及bb 与b 相遇而成bbb 图象时会产生重复计数。

当aaa 图象与bbb 图象恰出现一个时，重复因子为2；（1

2[1]N q C q =-）当图象aaa 与图象bbb 同时出现时，重复因子为4。所以1

22222227!6!6!5!5!35803!3!3!3!3!

A B A C B C C ??===

-+--= ??? 因为222A B C 为aa ，bb ，cc 图象出现的排列集合，当我们将aa 与a ，bb 与b ，cc 与c 看作不同的三对元素进行排列时，在aa 与a 相遇而成aaa 图象，bb

与b 相遇而成bbb 图象，cc 与c 相遇而成ccc 图象时会产生重复计数。

当aaa ，bbb ，ccc 图象恰出现一个时，重复因子为2；（1112233[1]N q C q C q =-+）

当aaa ，bbb ，ccc 图象恰出现两个时，重复因子为4；（2233[2]

N q Cq =-）当aaa ，bbb ，ccc 图象恰同时出现时，重复因子为8；

所以，()()222

336!5!5!5!(4!4!4!)3!34!4!4!3!73!282

A B C C C C =-++-+++-++--= 故，根据逐步淘汰原理，相同字母互不相邻的排列共有：

()()222222222222222

168039803580282198

A B C S A B C A B A C B C A B C =-+++++-=-?+?-=

8．把1,2,,n 排成一圈，令()f n 表示没有相邻数字恰好是自然顺序的排列数。（1）求()f n ；

（2）证明()(1)n f n f n D ++=。

解（1）问题等价于在排列中，数i 不能排在数1i +之前，1,2,,i n = 。

i n =时，11i +=。

用S 表示所有无重圆排列的集合，并设性质i P 表示在圆排列中具有(1)i i + 形式的性质，令{|,}i i A x x S x P =∈具有性质，1,2,,i n = 。

视(1)i i +为一个整体，立即可得(2)!i A n =-，1,2,,i n = ，

现计算()i j A A i j ≠，这种排列里同时含有(1)i i +和(1)j j +两种形式，不妨设i j <，则只可能是以下情况中的一种：

① 1j i ≠+，则成为2n -个元素的圆排列，其个数为(3)!n -； ② 1j i =+，则排列中出现(1)(2)i i i ++，看为一个元素，这样的圆排列

也有(3)!n -个；

③ ,1j n i ==，则此时1j i +=，同②类似，也有(3)!n -个；这三种情况不可能同时出现，所以(3)!i j A A n =-，

同理可得：(4)!i j k A A A n =-，…，12((1))!1n A A A n n =-+=

所以，

12121111222112()(1)(1)!(2)!(3)!(1)1!(1)0!(1)(1)!

!!!(1)!(2)!(3)!(1)1!(1)!2!(2)!(2n n

n i i j i j k n

i i j n

i j k n

n n n n n n

n n n n n n f n A A A S A A A A A A A A A n C n C n C C C n n n n n n n n n =≤<≤≤<<≤-----==-+

++-=---+--+-+-+--=--

-+--+----∑∑

∑

121

1!(1)0!

)!2!(1)!1!

111111

!(1)(1)1!(1)2!(2)3!(3)(2)!2!(1)!1!n n n n n n n n n n n n ---+--??=-+-++-+-??-----??

（2）证明()(1)n f n f n D ++=。

12()(1)

111111!(1)(1)1!(1)2!(2)3!(3)(2)!2!(1)!1!111111(1)!(1)(1)11!2!(1)3!(2)(1)!2!!1!11111!(1)1!(1)2!(2)3!(3)(n n n n

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

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

121

(1)2)!2!(1)!1!111111!(1)(1)11!2!(1)3!(2)(1)!2!!1!111111

!(1)(1)1!(1)2!(2)3!(3)(2)!2!(1)!1!111!11!n n n

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

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

2!1!(1)3!2!(2)1111(1)(1)(1)!(2)!2!!(1)!1!11111!1(1)(1)1!2!3!

(1)!!n n n n n

n n n n n n n D n n --?????+-+? ? ?

--?????

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

? ?---?????

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

9．n 个单位各派两名代表出席一个会议，2n 位代表围圆桌而坐，试问：（1）同一单位的代表相邻而坐的方案数是多少？（2）同一单位的代表互不相邻的方案数又是多少？解：（1）同一单位的两名代表相邻而坐，可看为一个，

问题即：n 个代表的圆排列，则方案数有：(1)!n - 种。

又同一单位的两名代表A 、B ，相邻而坐有两种方式，AB ，或BA ，共有n 个单位，故总的方案数有：2(1)!n n -（种）。

（2）设S 为所有2n 个人的无重圆排列，显然(21)!S n =-

i A 表示第i 个单位的两个代表相邻的方案数，1,2,,i n = ，

则12k i i i A A A ∑ 表示有k 个单位的代表相邻而坐的所有方案数，

可以这样得到：先在n 个单位中任选出k 个单位，有???

??k n 种选法；

其次让选出的这k 个单位的两个代表一定相邻，故每个单位的两个人可看作是一个人，而其余n k -个单位的22n k -个代表不一定相邻，因此这相当于222n k k n k -+=-个人做圆排列，有(21)!n k --种排法；另外，两个代表一定相邻的k 个单位，每个单位的两人做全排列，有2种排法，k 个单位共有2k 种排法；故按乘法原理，12(21)!2k k i i i n A A A n k k ??

=-- ???

∑

因此，根据容斥原理，各单位的两人互不相邻的方案数为：

121

(1)

(1)(21)!2k n n

k k k i i i i k k i n A S A A A n k k -===??

=--=--- ???

∑∑

∑ 。

10．一书架有m 层，分别放置m 类不同种类的书，每层n 册，现将书架上的图

书全部取出整理，整理过程中要求同一类的书仍然放在同一层，但可以打乱顺序，试问：

（1）m 类书全不在各自原来层次上的方案数是多少？（2）每层的n 本书都不在原来位置上的方案数是多少？

（3）m 层书都不在原来层次，每层n 本书也不在原来位置上的方案数又是多

少？

解：（1）先将层号错排，m 层的错排数是m D ；

再将每层的n 册书做全排列，有!n 种排法，m 层共有(!)m n 种排法，故按乘法原理，m 类书全不在各自原来层次上的方案数为：

(!)m m D n （种）

（2）先在m 层中任选出k 层0,1,2,,k m = ，有(,)C m k 种选法，

让选出的这k 层不在各自原来的层次上，即k 层做错排，错排数是k D ，其各层的n 册书做全排列，有!n 种排法，k 层共有(!)k n 种排法；其次让剩下的m k -层都在各自原来的层次上，但每层的n 本书都不在原来位置上，因此这相当于n 本书做错排，错排数是n D ，m k -层共计

有()m k n D - 种排法，

因此，当k 固定时，按乘法原理，有(,)(!)()k m k k n C m k D n D - 种排法。最后，按加法原理，每层的n 本书都不在原来位置上的方案数为：

m n k k m

k D n D k m -=∑???

? ??)()!(0 （种）（3）m 层书都不在原来层次，这相当于m 层做错排，错排数是m D ；

每层n 本书也不在原来位置上，这相当于n 本书做错排，错排数是n D ， m 层共计有()m n D 种排法；

因此，按乘法原理，m 层书都不在原来层次，每层n 本书也不在原来位置上的方案数为：()m m n D D （种）。

11．证明错排数的下列性质（2n ≥）：（1） 21(1)()n n n D n D D --=-+ （2） 1(1)n n n D nD -=+-

证明：

（1）2121211

1(1)()

111(1)(2)!1(1)1!2!(2)!111(1)!1(1)1!2!

(1)!1111(1)!1(1)(1)(1)1!2!

(2)!(1)!111(1)(1)!1(1)1!2!

(n n n n n n n n n D D n n n n n n n n n n ---------+???

=---+-+-? ?

-????

??+--+-+-?

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

--??+---+-+- 111

1)!1111(1)!1(1)(1)(1)1!2!

(1)!!n n n n n n n

n D n D n n D ---??

-????

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

（2）

1111

1!1(1)1!2!

!1111(1)!1(1)!(1)1!2!

(1)!!(1)n n n n n

n D n n n n n n n nD --??=-+-+- ?

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

-??=+-

12．n 个人参加一晚会，每人寄存一顶帽子和一把雨伞，会后各人也是任取一顶

帽子和一把雨伞，问：

（1）有多少种可能使得没有人能拿到他原来的任一件物品？（2）有多少种可能使得没有人能同时拿到他原来的两件物品？解：（1）由错排问题的结果，没有人拿回自己原来的帽子有n D 种可能，

没有人拿回自己原来的伞也有n D 种可能，这两件事情是互相无关的，由乘法法则可知，没有人拿到他原来的两件物品的方案数为：2n D （种）。（2）设S 表示所有可能的方案的集合，则2(!)S n =，

设i A 表示第i 人同时取回自己原来两件物品的方案的集合，1,2,,i n = 则 ()122

()!k k i i i R A A A n k ==- ，1,2,,k n = ，根据容斥原理，所求的方案数为：

()()()

21212222

2(!)(1)12(!)(1)!(2)!(1)0!12n n n

n n n n A A A n R R R n n n n n n n n ??????=-+++- ? ? ???????

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

第二版部分题 15．（题目略）

解：扫地、整理桌椅、擦窗子、擦黑板四项工作分别用w1,w2,w3,w4表示，

该题对应的带有禁区的棋盘如下：

甲

乙丙丁

则，223()(12)(12)1452R A x x x x x x =+++=+++

故安排工作的方案有：1234[]4!()3!()2!()1!()0!

4!43!52!21!00!8

N B r A r A r A r A =-+-+=-+-+= （种）

16．（题目略）

则，23

()17147

R A x x x

=+++

故：

123456

[]6!()5!()4!()3!()2!()1!()0!

6!75!144!73!

174

N B r A r A r A r A r A r A =-+-+-+

=-+-

故抽签结果使大家都满意的概率为：174/6! = 0.2417.

(完整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个相同种类的水果。

组合数学课后答案

作业习题答案习题二 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。证明：

组合数学第二章

课堂中的“空白”艺术所谓“空白”，就是指空着，没有被填满或没有被利用的部分。在绘画艺术中就有一种美叫做空白美。那么以此为鉴，在课堂教学中也有一种方法称之为——“空白”艺术。现代教育理论认为，数学教学要提供给学生充分体验与交流的机会，使他们真正理解和掌握数学思想和方法。走进新课标，教学的最高宗旨和核心理念是“一切为了每一个学生的发展”。而“发展”是一个生成性的动态过程，作为教师要不断地为学生创设一种“可持续发展”的时间与空间。特别是伴随着新一轮基础教育课程改革的实施和推进，教师的教学行为和学生的学习方式都发生了巨大的改变。在课堂上，教育者要善于适时、适度地巧设“空白”，秉承“学生只有通过自己的真切体验，才能真正对所学内容有所感悟，进而内化为己有，在学习活动实践中逐步学会学习”的课改理念，让学生自主、合作、探究地学习，使他们充分发挥自己的创造性，尽情展示、描绘出属于他们的精彩。教学内容：北京市21世纪教材九年义务教育教材数学实验本第1册第十一单元《统计初步知识》。 [片段一] 课堂练习1：猜丁克游戏（石头、剪子、布）。师：大家玩过这个游戏吗？（学生辨认游戏中的手势。）下面请同座位的两个人为一组玩这个游戏，要求统计出你们各自赢的次数填入表格中。学生一边玩一边用自己喜欢的方式记录如下：第一种用符号表示：…… 第二种用画图表示：…… 第三种用实物表示：小棒、学具卡片……

第四种用数字表示：1、2、3、…… 第五种用“正”字表示。学生游戏后，在实物投影上展示自己的记录方式并汇报统计结果。 [评析：这里老师只是提出了学习任务，即“统计出你们各自赢的次数填入表格中”，但对于学习方式即怎样统计、如何记录并没有作出任何要求。因此为学生创设了创新实践的空间，这样的“留白”使学生能够得以彰显其鲜明的个性，并满足其渴望同辈群体认可的价值需求。] [片段二] 课堂练习3：数一数屋里一共有多少个小朋友？学生提出质疑：屋外的这些鞋摆放得太乱了！不好数，能不能摆整齐再数呀？师：题目要求是数人，你们为什么想到要数鞋呢？生：因为有一双鞋就等于有一个人。师：（数出人数后）你们想对屋里的小朋友说些什么吗？生1：你们乱放鞋子，出门时容易被鞋子拌倒，不安全。生2：你们应该做文明的好孩子。生3：你们要养成把东西摆放整齐的好习惯。 [评析：作为变式统计练习，这里一方面留有学生逻辑推理的空白，即“有一双鞋就等于有一个人”，渗透“透过现象看本质”的辨证思想；另一方面又留有学生情感、态度的空白，即“你们想对屋里的小朋友说些什么吗？”，由题及事，以事为载体，培养学生正确看待问题的态度以及要做文明好孩子的情感。] 以上两个片段，在教师的巧妙布白之中，学生们各抒己见，主动

清华组合数学()习题答案

?1.证：对n 用归纳法。先证可表示性：当n=0,1时，命题成立。假设对小于n 的非负整数，命题成立。对于n,设k!≤n ＜(k+1)!,即0≤n-k!＜k·k!由假设对n-k!,命题成立，设n-k!=∑a i ·i!，其中a k ≤k-1,n=∑a i ·i!+k!，命题成立。i=1 k i=1 k 再证表示的唯一性：设n=∑a i ·i!=∑b i ·i!, 不妨设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!,(a j -b j )·j!=∑(b i -a i )·i!≥j!＞∑i·i!≥∑|b i -a i |·i!≥∑(b i -a i )·i! 另一种证法：令j=min{i|a i ≠b i }∑a i ·i!=∑b i ·i!,两边被(j+1)!除,得余数a j ·j!=b j ·j!,矛盾. i=1 k i=1k i=1 j-1i=1 j-1 i=1j-1i=1 j-1 i ≥j i ≥j ?2.证：组合意义：等式左边：n 个不同的球，先任取出1个，再从余下的n-1个中取r 个；等式右边：n 个不同球中任意取出r+1个，并指定其中任意一个为第一个。显然两种方案数相同。 nC(n-1,r) = n ————= ——————— (n-1)! (r+1)·n! r!·(n-r-1)! (r+1)·r!·(n-r-1)! = ——————= (r+1)C(n,r+1).(r+1)·n! (r+1)!·(n-r-1)! ?3.证：设有n 个不同的小球，A 、B 两个盒子,A 盒中恰好放1个球,B 盒中可放任意个球。有两种方法放球： ①先从n 个球中取k 个球(k ≥1),再从中挑一个放入A 盒,方案数共为∑kC(n,k),其余球放入B 盒。 ②先从n 个球中任取一球放入A 盒，剩下n-1个球每个有两种可能，要么放入B 盒，要么不放，故方案数为n2 . 显然两种方法方案数应该一样。 k=1n n-1 ?4.解：设取的第一组数有a 个,第二组有b 个,而要求第一组数中最小数大于第二组中最大的，即只要取出一组m 个数(设m=a+b),从大到小取a 个作为第一组,剩余的为第二组。此时方案数为C(n,m)。从m 个数中取第一组数共有m-1中取法。总的方案数为∑(m-1)C(n,m)=n ·2 +1. ?5.解：第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种方案。 m=2 n n-1 ?6.解：首先所有数都用6位表示，从000000到 999999中在每位上0出现了10 次,所以0共出现了6·10 次,0出现在最前面的次数应该从中去掉， 000000到999999中最左1位的0出现了10 次， 000000到099999中左数第2位的0出现了10 次， 000000到009999左数第3位的0出现了10 次, 000000到000999左数第4位的0出现了10 次, 000000到000099左数第5位的0出现了10 次, 000000到000009左数第6位的0出现了10 次。另外1000000的6个0应该被加上。所以0共出现了 6·10 –10 –10 –10 –10 –10 –10 +6 = 488895次。 5 5 5 4 3 2 1 5543210 ?7.解：把n 个男、n 个女分别进行全排列，然后按乘法法则放到一起，而男女分别在前面,应该再乘2,即方案数为2·(n!) 个. 围成一个圆桌坐下，根据圆排列法则，方案数为2 ·(n!) /(2n)个. ?8.证：每个盒子不空，即每个盒子里至少放一个球，因为球完全一样，问题转化为将n-r 个小球放入r 个不同的盒子，每个盒子可以放任意个球，可以有空盒，根据可重组合定理可得共有C(n-r+r-1,n-r) = C(n-1,n-r)中方案。根据C(n,r)=C(n,n-r),可得 C(n-1,n-r)=C(n-1,n-1-(n-r))=C(n-1,r-1)个方案。证毕。 2 2 ?9.解：每个能整除尽数n 的正整数都可以选取每个素数p i 从0到a i 次，即每个素数有a i +1种选择，所以能整除n 的正整数数目为(a 1+1)·(a 2+1)·…·(a l +1)个。 ?10.解：相当于把n 个小球放入6个不同的盒子里，为可重组合，即共有C(n+6-1,n)中方案，即C(n+5,n)中方案。 ?11.解：根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有C(10,4)中,即交于210个点。

排列组合习题-(含详细答案)

圆梦教育中心排列组合专项训练 1.题1 (方法对比，二星) 题面：(1)有5个插班生要分配给3所学校，每校至少分到一个，有多少种不同的分配方法？ (2)有5个数学竞赛名额要分配给3所学校，每校至少分到一个名额，有多少种不同的名额分配方法？解析：“名额无差别”——相同元素问题 (法1)每所学校各分一个名额后，还有2个名额待分配，可将名额分给2所学校、1所学校，共两类： 2 1 33C C +(种) (法2——挡板法) 相邻名额间共4个空隙，插入2个挡板，共： 246C =(种) 注意：“挡板法”可用于解决待分配的元素无差别，且每个位置至少分配一个元素的问题.(位置有差别，元素无差别) 同类题一题面：有10个运动员名额，分给7个班，每班至少一个,有多少种分配方案？答案：6 9C 详解：因为10个名额没有差别，把它们排成一排。相邻名额之间形成9个空隙。在9个空档中选6个位置插个隔板，可把名额分成7份，对应地分给7个班级，每一种插板方法对应一种分法共有69C 种分法。同类题二题面：求方程X+Y+Z=10的正整数解的个数。答案：36. 详解：将10个球排成一排，球与球之间形成9个空隙，将两个隔板插入这些空隙中（每空至多插一块隔板），规定由隔板分成的左、中、右三部分的球数分别为x 、y 、z 之值, 故解的个数为C 92=36（个）。 2.题2 (插空法，三星) 题面：某展室有9个展台，现有3件展品需要展出，要求每件展品独自占用1个展台，并且3件展品所选用的展台既不在两端又不相邻，则不同的展出方法有______种；如果进一步要求3件展品所选用的展台之间间隔不超过两个展位，则不同的展出方法有____种. 答案：60，48 同类题一题面： 6男4女站成一排，任何2名女生都不相邻有多少种排法？答案：A 66·A 47种. 详解：任何2名女生都不相邻，则把女生插空，所以先排男生再让女生插到男生的空中，共有A 6 6·A 4 7种不同排法．同类题二题面：有6个座位连成一排，现有3人就坐，则恰有两个空座位相邻的不同坐法有( ) A ．36种 B ．48种 C ．72种 D ．96种答案：C. 详解：恰有两个空座位相邻，相当于两个空位与第三个空位不相邻，先排三个人，然后插空，从而共A 33A 2 4＝72种排法，故选C. 3．题3 (插空法，三星) 题面：5个男生到一排12个座位上就座，两个之间至少隔一个空位． 1]没有坐人的7个位子先摆好， [2](法1——插空)每个男生占一个位子，插入7个位子所成的8个空当中，有： 58A =6720种排法. (法2)[1]5个男生先排好：55A ； [2]每个男生加上相邻的一个座位，共去掉9个位置，当作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个相同种类的水果。

李凡长版-组合数学课后习题答案-习题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

组合数学习题4(共5章)

第四章生成函数 1. 求下列数列的生成函数：（1）{0,1,16,81,…,n 4,…} 解：G{k 4 }= 235 (11111) 1x x x x x +++-（）（2）343,,,333n +?????????? ? ? ????? ???? 解：3n G n +?????? ?????=4 1(1)x - （3）{1,0,2,0,3,0,4,0,……} 解：A(x)=1+2x 2+3x 4+4x 6+…=2 1 1x -. （4）{1,k ,k 2,k 3,…} 解：A(x)=1+kx+k 2x 2+k 3x 3+…= 1 1kx -. 2. 求下列和式：（1）14+24+…+n 4 解：由上面第一题可知，{n 4}生成函数为 A(x)=235 (11111)1x x x x x +++-（）=0 k k k a x ∞=∑，此处a k =k 4 .令b n =14 +24 +…+n 4 ，则b n =0n k k a =∑，由性质3即得数列{b n }的生成函数为 B(x)= 0n n n b x ∞ =∑=() 1A x x -=34 125(1111)i i i x x x x x i ∞ =++++?? ??? ∑. 比较等式两边x n 的系数，便得 14+24+…+n 4 =b n =1525354511111234n n n n n n n n -+-+-+-++++----???????? ? ? ? ? ???????? 321 (1)(691)30 n n n n n =+++- （2）1·2+2·3+…+n (n +1) 解：{ n (n +1)}的生成函数为A(x)= 3 2(1)x x -=0 k k k a x ∞ =∑，此处a k = n (n +1). 令b n =1·2+2·3+…+n (n +1)，则b n =0 n k k a =∑.由性质3即得数列{b n }的生成函数为B(x)= n n n b x ∞ =∑= () 1A x x -= 4 2(1)x x -=032n k k k x x k =+?? ?? ?∑. 比较等式两边x n 的系数，便得

组合数学与图论复习题及参考答案

组合数学与图论复习题及答案 1．Show that if n+1 integers are chosen form the set {1,2, …,2n},then there are always two which differ by at most 2. 从{1,2, …,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到 2n之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k大的另一个数。 2．Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100. 设52个整数a1，a2，…，a52被100除的余数分别是r1,r2,…,r52，而任意一个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将r1,r2,…,r52放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj，要么有ri＋rj ＝100，也就是说ai－aj|100或者ai＋aj|100。 3．从1，2，3，…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。鸽子洞原理，必有两个数相邻，相邻的两个数互质 4．Prove that Ramsey number R(p,q)≤R(p,q-1)+R(p-1,q). 令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者F中有 R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)≤ R(p,q-1)+R(p-1,q) 5．There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。从10人中随意选一个人p，F表示与p相识的人，S表示与p不相识的人若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6．In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats? 6个男的先进行圆排列，然后6个女的插入空位。 7．In how many ways can 15 people be seated at round table if B refuses to sit next to A? What if B only refuses to sit on A right?

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

1 第一章排列组合 1、在小于2000的数中，有多少个正整数含有数字2？解：千位数为1或0，百位数为2的正整数个数为：2*1*10*10；千位数为1或0，百位数不为2，十位数为2的正整数个数为：2*9*1*10；千位数为1或0，百位数和十位数皆不为2，个位数为2的正整数个数为：2*9*9*1；故满足题意的整数个数为：2*1*10*10+2*9*1*10+2*9*9*1＝542。 2、在所有7位01串中，同时含有“101”串和“11”串的有多少个？解：（1）串中有6个1：1个0有5个位置可以插入：5种。（2）串中有5个1，除去0111110，个数为()6 2 -1＝14。（或： ()()41 42 *2+＝14）（3）串中有4个1：分两种情况：①3个0单独插入，出去1010101，共()53 -1 种；②其中两个0一组，另外一个单独，则有 ()()2*)2,2(41 52 -P 种。（4）串中有3个1：串只能为**1101**或**1011**，故共4*2种。所以满足条件的串共48个。 3、一学生在搜索2004年1月份某领域的论文时，共找到中文的10篇，英文的12篇，德文的5篇，法文的6篇，且所有的都不相同。如果他只需要2篇，但必须是不同语言的，那么他共有多少种选择？解：10*12+10*5+10*6+12*5+12*6+5*6 4、设由1，2，3，4，5，6组成的各位数字互异的4位偶数共有n 个，其和为m 。求n 和m 。解：由1，2，3，4，5，6组成的各位数字互异，且个位数字为2，4，6的偶数均有P(5,3)=60个，于是：n = 60*3 = 180。以a 1,a 2,a 3,a 4分别表示这180个偶数的个位、十位、百位、千位数字之和，则 m = a 1+10a 2+100a 3+1000a 4。因为个位数字为2，4，6的偶数各有60个，故 a 1 = (2+4+6)*60=720。因为千（百，十）位数字为1，3，5的偶数各有3*P(4,2) = 36个，为2，4，6的偶数各有2*P(4,2) = 24个，故 a 2 = a 3 = a 4 = (1+3+5)*36 + (2+4+6)*24 = 612。因此， m = 720 + 612*(10 + 100 + 1000) = 680040。 5、从{1，2，…，7}中选出不同的5个数字组成的5位数中，1与2不相邻的数字有多少个？解：1与2相邻：())4,4(253P ??。故有1和 2 但它们不相邻的方案数： ()())4,4(2)5,5(53 5 3 P P ??-? 只有1或2：())5,5(254P ?? 没有1和2：P(5,5)

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

第二章容斥原理与鸽巢原理 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| = 5143 2、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 = 9927 3、1到10000之间（不含两端）能被4和5整除，但不能被7整除的整数有多少个？解令A 1表示在1与10000之间能被4和5整除的整数集，A 2表示4和5整除，也能被7整除的整数集。则： |A 1| = L 10000/20」= 500, |A 2| = L 10000/140」= 71, 所以1与10000之间能被4和5整除但不能被7整除的整数的个数为：500-71=429。 4、计算集合{2·a, 3·b, 2·c, 4·d }的5组合数. 解令S ∞={∞·a, ∞·b,∞·c,∞·d}，则S 的5组合数为()1455 -+ = 56 设集合A 是S ∞的5组合全体，则|A|＝56，现在要求在5组合中的a 的个数小于等于2，b 的个数小于等于3，c 的个数小于等于2，d 的个数小于等于4的组合数. 定义性质集合P={P 1,P 2,P 3,P 4},其中： P 1：5组合中a 的个数大于等于3； P 2：5组合中b 的个数大于等于4； P 3：5组合中c 的个数大于等于3； P 4：5组合中d 的个数大于等于5. 将满足性质P i 的5组合全体记为A i (1≤i ≤4). 那么，A 1中的元素可以看作是由 S ∞的5－3＝2组合再拼上3个a 构成的，所以|A 1| =()142 2 -+ = 10.

排列组合练习题及.答案

《排列组合》一、排列与组合 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的五个杯盖，将五个杯盖盖在五个茶杯上，至少有两个杯盖和茶杯的编号相同的盖法有 A.30种 B.31种 C.32种 D.36种 5.从编号为1，2，…，10,11的11个球中取5个，使这5个球中既有编号为偶数的球又有编号为奇数的球，且它们的编号之和为奇数，其取法总数是 A.230种 B.236种 C.455种 D.2640种 6.从6双不同颜色的手套中任取4只，其中恰好有1双同色的取法有 A.240种 B.180种 C.120种 D.60种 7. 用0，1，2，3，4，5这六个数组成没有重复数字的四位偶数，将这些四位数从小到大排列起来，第71个数是。三、间接与直接 1.有4名女同学，6名男同学，现选3名同学参加某一比赛，至少有1名女同学，由多少种不同选法？ 2. 6名男生4名女生排成一行，女生不全相邻的排法有多少种？ A B含有4个元素，试求同时满足下列两个条件的集合C的个数：（1） 3.已知集合A和B各12个元素， ? () C A B C A≠?,?表示空集。且C中含有三个元素；（2） 4. 从5门不同的文科学科和4门不同的理科学科中任选4门，组成一个综合高考科目组，若要求这组科目中

组合数学练习题_带答案

组合数学练习题第一章排列组合 1, 在1到10000之间，有多少个每位上数字全不相同而且由偶数构成的整数？本题分为四种情况: 1位整数有4个: 2, 4, 6, 8 2位整数有4*4种方案, 有16个 3位整数有4*4*3种方案, 有48个 4位整数有4*4*3*2种方案, 有96个总共有4+16+48+96=164个这样的整数. 2, 一教室有两排，每排9个坐位，今有14名学生，问按下列不同的方式入座，各有多少种坐法？(1) 规定某5人总坐在前排，某4人总在后排，但每人具体坐位不指定；(2) 要求前排至少坐5人，后排至少坐4人。 (1)本问中, 第一排和第二排各有5名和4名同学被确定, 那么14名同学中还有5名同学没有固定在哪一排, 所以可以根据这5名同学的不同排列来计算, 分5种情况考虑; 1) 从这5名同学中选出4名同学坐在第一排, 这4名和固定的5名同学进行全排列、另外1名同学和第二排固定的4名同学进行全排列，以此类推；2) 从5名同学中选出3 名同学坐第一排; 3) 从5名同字中选出2名同学坐第一排; 4) 从5名同学中选出1名同学坐第一排; 5) 最后5名同学全部坐在第二排; 把这5种情况的坐法安排数全部加起来就是结果. C(5,4)*P(9,9)*P(9,5)+C(5,3)*P(9,8)*P(9,6)+C(5,2)*P(9,7)*P(9,7)+ C(5,1)*P(9,6)*P(9,8)+P(9,5)*P(9,9) (2)本问中, 第一排和第二排所坐的同学的数量被确定, 分别是5名和4名, 那么要从14 名同学中把省下的5名同学选出来, 然后再按照坐在不同排的情况进行计算, 同样分5 种情况考虑; 1) 从这5名同学中选出4名同学坐在第一排, 这4名和固定的5名同学进行全排列、另外1名同学和第二排固定的4名同学进行全排列，以此类推；2) 从5 名同学中选出3名同学坐第一排; 3) 从5名同字中选出2名同学坐第一排; 4) 从5名同学中选出1名同学坐第一排; 5) 最后5名同学全部坐在第二排; 把这5种情况的坐法安排数全部加起来再乘以从14名同学中任选出5名同学方法的数就是结果. C(14,5)*[P(9,9)*P(9,5)+P(9,8)*P(9,6)+P(9,7)*P(9,7)+P(9,6)*P(9,8)+ P(9,5)*P(9,9)] 3, n对夫妇,要求排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？围一圆桌而坐且要求每对夫妇坐在一起,又有多少种方案? (1)本问中, 男女各有n名, 分别进行全排列各有n!种方案, 将他们交叉排列就有(n!)2种方案, 同时男在女前或女在男前又是不同的方案, 所以要乘以2, 所以方案数为--- 2 (n!)2 (2)本问较第一问要去掉变为圆周排列后的重复度, 总的人数为2n, 用第一问的方案数除以2n, 所以方案数为--- (n!)2/n (3)本问中, 每对夫妇交换位置坐的方案数为2n, 再把每对夫妇看成单个元素进行圆周全排列, 方案为n!/n, 最后把两种方案数相乘, 所以方案数为--- 2n n!/n 4, 有16名选手，其中6名只能打后卫，8名只能打前锋，2名能打前锋或后卫，今欲选出11人组成一支球队，而且需要7人打前锋，4人打后卫，试问有多少种选法？根据2名既能打前锋也能打后卫选手的不同情况来计算方案

组合数学课后答案

习题二 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个相同种类的水果。

组合数学+卢开澄版++答案第二章

2.1 求序列{0，1，8，27，…3n …}的母函数。解：()() ++++++=++++++=n n n x n x x x x G x a x a x a x a a x G 3323322102780 ()0464143213 13 =+-+--==-----n n n n n n n a a a a a n a n a 左右同乘再连加： 0464:0 464:0 464: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 母函数：()()42 162036-+-=x x x x G 2.2 已知序列()()3433{,,……()33,,n +……}，求母函数。解：1(1) n x -的第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 B x A ++- 从而有： ???-==????=-=+4 778963B 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 x

n a =7*n )6(*49n -- 2.4．已知母函数239156x x x ---，求对应的序列{}n a 。解：母函数为239()156x G x x x -= --39(17)(18)x x x -=+- A B G(x)17x 18x A(18x)B(17x)39x = ++--++=-令 A B 38A+7B=9+=??--? 解得：A=2 B=1 所以 i i i 0i 0 21G(x)2*(7x)(8x)17x 18x ∞∞===+=-++-∑∑ n n n a 2*(7)8=-+ 2.5 设n n F G 2=，其中F n 是第n 个Fibonacci 数。证明：0321=+---n n n G G G ， n =2，3，4…。求},,,{210 G G G 的母函数。解：设 ++++=332210)(x G x G x G G x H ，则 44332210)(x G x G x G x G G x H ++++= ……① ++++=43322103333)(3x G x G x G x G x xH ……② +++=4231202)(x G x G x G x H x ……③ ①-②+③，得： ()x G x G G x H x x 01023)(31-+=+- 又已知 n n F G 2=，则 000==F G ，121==F G 所以，)2 53)(253(31)(2x x x x x x x H ---+=+-= 设x B x A x H --+-+=253253)(，则可列出方程组：

组合数学(西安电子科技大学(第二版))习题4答案

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

最新组合数学习题解答

组合数学课后答案

组合数学第二章

清华组合数学()习题答案

排列组合习题-(含详细答案)

组合数学课后标准答案

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

组合数学习题4(共5章)

组合数学与图论复习题及参考答案

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

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

排列组合练习题及.答案

组合数学练习题_带答案

组合数学 课后答案

组合数学+卢开澄版++答案第二章

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

组合数学课后答案