当前位置:文档之家› 组合数学课后答案

组合数学课后答案

组合数学课后答案
组合数学课后答案

作业习题答案

习题二

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)行

1

1

2

m

m

+

??

+

?

??

列的网格每个格子涂1种颜色,有m种颜色可以

选择,证明:无论怎么涂色,其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。

证明:

(1)对每一列而言,有(m+1)行,m种颜色,有鸽巢原理,则必有两个单元格颜色相同。

(2)每列中两个单元格的不同位置组合有

1

2

m+

??

?

??

种,这样一列中两个同色单元格的位

置组合共有

1

2

m

m

+

??

?

??

种情况

(3)现在有112m m +??

+

???

列,根据鸽巢原理,必有两列相同。证明结论成立。 2.11证明:从S={1,3,5,…,599}这300个奇数中任意选取101个数,在所选出的数中一定存在2个数,它们之间最多差4。 证明:

将S 划分为{1,3,5},{7,9,11}……,{ 595,597,599}共100组,由鸽巢原理知任意选取101个数中必存在2个数来自同一组,即其差最多为4.

2.12证明:从1~200中任意选取70个数,总有两个数的差是4,5或9。 设从1~200中任意选取的70个数构成一组,即 第一组: 1270,,,a a a ;

第二组: 12704,4,,4a a a +++ ; 第三组:12709,9,,9a a a +++ ;

显然,这三组数均在1~209之间,且共有3*70=210个数,根据鸽巢原理一定有两个数相等,又因为任取的这70个数均不相同,所以这2个相等的数一定来自不同组,根据不同组的分布讨论如下:

1) 如果这两个数分别来自第一组和第二组,则有4j i a a =+; 2) 如果这两个数分别来自第一组和第三组,则有9j i a a =+; 3) 如果这两个数分别来自第二组和第三组,则有5j i a a =+;

得证。

习题三

3.8 确定多重集{3,4,5}M a b c =???的11-排列数?

11!11!11!

277203!4!4!3!3!5!2!4!5!

++=

3.9 求方程123420x x x x +++=,满足12342,0,5,1x x x x ≥≥≥≥-的整数解的个数。

14416803+-??= ???

3.10 架上有20卷百科全书,从中选出4卷使得任意两本的卷号都不相邻的选法有多少种?

解:n=20,r=4,1204117238044n r r -+-+??????=== ? ? ???????

3.17 一局乒乓球比赛中,运动员甲以11:7战胜运动员乙,若在比赛过程中甲从来没有落后

过,求有多少种可能的比分记录?

解:根据题意,相当于求从点(0,0)到点(11,7)且从下方不穿过y=x 的非降路径数,即为:

11711171(117)!(1171)

-13260 10 12(111)!7!+-+-????+-+=

= ? ?+????

3.21 1)会议室中有2n +1个座位,现摆成3排,要求任意两排的座位都占大多数,求有多少

种摆法? 解:

(1)

方法1:如果没有附加限制则相当于把2n+1个相同的小球放到3个不同的盒子里,有

213123 3-1 2n n ++-+????= ? ?????

种方案,而不符合题意的摆法是有一排至少有n+1个座位。这相当于将n+1个座位先放到3排中的某一排,再将剩下的2n+1-(n+1)=n 个座位任意分到3排中,这样的摆法共有21(1)31233 2 2n n n +-++-+????

?=? ? ?????

种方案,所以符合题意的摆

法有:

23213 2 2 2n n n +++??????

-?= ? ? ???????

方法2:设第一排座位有x 1个,第二排座位有x 2个,第三排座位有x 3个。x 1+x 2+x 3=2n+1,且x 1+x 2≥(2n+1)/2,x 1+x 3≥(2n+1)/2,x 2+x 3≥(2n+1)/2,即x 1+x 2≥n+1,x 1+x 3≥n+1,x 2+x 3≥n+1,令y 1= x 1+x 2-n-1,y 2= x 1+x 3-n-1,y 3= x 2+x 3-n-1,可知y 1+y 2+y 3=2(2n+1)-3(n+1)=n-1且y i ≥0,1≤i ≤3。显然,x 方程满足要求的解与y 方程非负整数解一一对应,有

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

种。

方法3:要求每行非空

如果没有附加限制则相当于把2n+1个相同的小球放到3个不同的盒子里,不允许为空,有2112 3-12n n +-????

=

? ?????

种方案,而不符合题意的摆法是有一排至少有n+1个座位。这相当

于将n 个座位先放到3排中的某一排,再将剩下的2n+1-n=n+1个座位任意分到3排中,每排不允许为空,这样的摆法共有21133 22n n n +--????

?=? ? ?????

种方案,所以符合题意的摆法

有:

21322 2n n n +??????

-?= ? ? ???????

(2)会议室中有2n 个座位,现摆成3排,要求任意两排的座位都占大多数,求有多少种摆法?

解:

(2)

方法1:如果没有附加限制则相当于把2n 个相同的小球放到3个不同的盒子里,有

23122 2 2n n +-+????= ? ?????

种方案,而不符合题意的摆法是有一排至少有n 个座位。这相当于将n 个座位先放到3排中的某一排,再将剩下的2n-n=n 个座位任意分到3排中,这样的摆法共有231233 2 2n n n -+-+????

?=?

? ?????

种方案。需要注意的是,三排中如果任意两排都是

n 个座位共有3种情况,这3种情况在23 2n +??

? ???

中被重复计算了2次,因此需要将重复减去的3次加上。所以符合题意的摆法有:

222133 2 2 2n n n ++-??????

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

方法2:设第一排座位有x 1个,第二排座位有x 2个,第三排座位有x 3个。x 1+x 2+x 3=2n ,且x 1+x 2≥n +1,x 1+x 3≥n +1,x 2+x 3≥n +1,令y 1=x 1+x 2-n-1,y 2=x 1+x 3-n-1,y 3=x 2+x 3-n-1,可知y 1+y 2+y 3=2(2n)-3n-3=n-3且y i ≥0,1≤i ≤3。显然,x 方程满足要求的解与y 方程非负整数解一一对应,有

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

种。 方法3:要求每行非空

如果没有附加限制则相当于把2n 个相同的小球放到3个不同的盒子里,不允许为空,

有21212 2n n --????= ? ?????

种方案,而不符合题意的摆法是有一排至少有n 个座位。这相当于将

n-1个座位先放到3排中的某一排,再将剩下的2n-(n-1)=n+1个座位任意分到3排中,每排不允许为空,这样的摆法共有2(1)13322n n n ---????

?=? ? ?????

种方案,所以符合题意的摆法

有:

2113 222n n n --??????

-?= ? ? ???????

3.24 n (n ≥2)个不同的球分给甲、乙、丙3人,使得甲至少分得两个球,有多少种不同的分法? 解:1

2322

2n

n

n

n n i

i n n i --=??--= ???

∑ 3.25 24个相同的球分堆,使得每堆的球不少于5,有多少种不同的分堆方法?

方法1:

24

5

24i

i i k

=?=∑

55266224242243(1())(1())(1()())

x x x x x x x ++++++++++ 5624

1

(1)(1)(1)

x x x =

--- 每堆去掉4个球,剩余球分堆的方法数

5

1

(244,)(20,1)(16,2)(12,3)(8,4)(4,5)18125026

i B i i B B B B B =-=++++=++++=∑

其中

(12,3)(9,1)(9,2)(9,3)

14(6,1)(6,2)(6,3)

1413(3,1)(3,2)(3,3)141311112

B B B B B B B B B B =++=++++=++++++=++++++=

(8,4)(4,1)(4,2)(4,3)(4,4)12115B B B B B =+++=+++=

习题四

4.3 一项对于A,B,C 三个频道的收视调查表明,有20%的用户收看A ,16%的用户收看B ,

14%的用户收看C ,8%的用户收看A 和B ,5%的用户收看A 和C ,4%的用户收看B 和C ,2%的用户都看。求不收看A,B,C 任何频道的用户百分比?

解:设性质P 1是收看A 频道的用户百分比;P 2是收看B 频道的用户百分比;P 3是收看C 频道的用户百分比;Ai={x|x ∈S ∧x 具有性质P i },i=1,2,3。S 是受调查的所有用户的集合。

||1S =;

123||20%,||16%,||14%A A A ===

121323||8%,||5%,||4%A A A A A A ?=?=?= 123||2%A A A ??=

根据定理4.1.1,有

123123121323123||||(||||||)(||||||)||1(20%16%14%)(8%5%4%)2%65%

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

4.4 某杂志对100名大学新生的爱好进行调查,结果发现他们喜欢看球赛和电影、戏剧。其

中58人喜欢看球赛,38人喜欢看戏剧,52人喜欢看电影,既喜欢看球赛又喜欢看戏剧的有18人,既喜欢看电影又喜欢看戏剧的有16人,三种都喜欢看的有12人,求有多少人只喜欢看电影? 解: 方法1:

设性质P 1喜欢看球赛;P 2喜欢看戏剧;P 3喜欢看电影。Ai={x|x ∈S ∧x 具有性质P i },i=1,2,3。

S 是100名大学新生的集合。

||100S =

123||58,||38,||52A A A ===

121323||18,||?,||16A A A A A A ?=?=?= 123||12A A A ??=

由题意可得,这100名大学生中每人至少有三种兴趣中的一种,

12312312132312313||||(||||||)(||||||)||100(583852)(18||16)120

A A A S A A A A A A A A A A A A A A ??=-+++?+?+?-??=-++++?+-= 所以可得既喜欢看球赛有喜欢看电影的人有

13||(583852)100(1816)1226A A ?=++--++=

因此只喜欢看电影的人有

12331323123||||||||||A A A A A A A A A A A ??=-?-?+??

=52-(26+16)+12=22人 方法2:

1231212||||||||||100(5838)1822A A A S A A A A ??=--+?=-++=

A

C

B

65

方法3:

设只喜欢看球赛的人数为x ;设只喜欢看电影的人数为y ;喜欢看球赛和电影但不喜欢看戏

剧的人数为z ,则

1003858185216x y z x z y z ++=-??

+=-??+=-?

解得y=22,所以22人只喜欢看电影。

4.5 某人有六位朋友,他跟这些朋友每一个都一起吃过晚餐12次,跟他们中任二位一起吃

过6次晚餐,和任意三位一起吃过4次晚餐,和任意四位一起吃过3次晚餐,任意五位一起吃过2次晚餐,跟六位朋友全部一起吃过一次晚餐,另外,他自己在外吃过8次晚餐而没碰见任何一位朋友,问他共在外面吃过几次晚餐? 解:设n 为在外面共吃过晚餐的次数,性质Pi(1≤i ≤6)表示他和第i 位朋友吃过晚餐,Ai(1≤i ≤6)

表示他和第i 位朋友吃过晚餐的次数。显然满足对称筛公式,其中

(1)12,(2)6,(3)4,(4)3,(5)2,(6)1,N N N N N N ======

由题可得方程:

123456

123456666666||12643218

A A A A A A n C C C C C C ?????=-?+?-?+?-?+?=解得吃饭次数为123456

6666661264321836C C C C C C ?-?+?-?+?-?+=

4.13 计算棋盘多项式

解:

2)+(1+x)*R(

)

球赛

戏剧

电影

= x3+3x2+x+(1+x)[xR()+R()]

= x3+3x2+x+(1+x)[x(1+x)+(1+4x+2x2)]

= 5x3+12x2+7x+1

4.14 A,B,C,D,E五种型号的轿车,用红、白、蓝、绿、黑五种颜色进行涂装。要求A型车不能涂成黑色;B型车不能涂成红色和白色;C型车不能涂成白色和绿色;D型车不能涂绿色和蓝色;E型号车不能涂成蓝色,求有多少种涂装方案?

解:

绿

绿

绿

1.若未规定不同车型必须涂不同颜色,则:

????=

涂装方案43334432

2.若不同车型必须涂不同颜色,则:

禁区的棋盘多项式为:

=R()R()=(1+x)(xR())

=(1+x)(xR()R()+R()R())

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

=1+8x+22x2+25x3+11x4+x5

所以:

N =5!-r1×4!+r2×3!–r3×2!+r4×1!- r5×0! =5!-8*4!+22*3!-25*2!+11*1!-1=20

习题五

5.1 求如下数列的生成函数。

(1))1()1(+-=k a k k ;(2)k k k k a 2)1(-=; (3)6+=k a k ; (4))2(+=k k a k ; (5)?

??

? ??+=k

k n a k ; (6)3k k a ??

= ???; 解:

12

00

1

(1)()(1)(1)[(1)]'[]'1(1)k

k

k k k k x A x k x x x x ∞

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

2(2)()(1)2(2)(12)

k

k

k

k k k k x

A x k x k x x ∞∞

==-=-=-=

+∑∑ 222

66665(3)()(6)6(1)1(1)(1)k

k

k k k k x x x x

A x k x kx x x x x x ∞∞∞

===+--=+=+=

+==

----∑∑∑ 1

2

323

1(4)()(2)(1)[]''[]'

1123(1)(1)(1)k

k k k k k x A x k k x x k k x

kx x x x x x x x x

x x x ∞∞

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

+=

---∑∑∑

1

01

(5)()(1)k k n k n k A x x k x ∞

-=+??== ?-??

∑ 323200

00023432

23323344

32111(6)()36623141(1)16(1)2(1)3(1)4332426(1)(1)k k k k k

k k k k k k k k k A x x x k x k x kx

x x x x x x x x x x x x x x x x x x x x ∞

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

--∑∑∑∑∑

3

303333340(6)()33333(1)k k k k k k k k k k k k k k A x x x x x x

k k k x x x k x ∞

∞∞∞

-====∞

=????????==== ? ? ? ?--????????

+??== ?

-??

∑∑∑∑∑

5.3 已知数列{}k a 的生成函数是x

x x x A 31932)(2

--+=,求k a .

20

2392()32331313k k k x x A x x x x x x ∞

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

9

1

23

1

k n

n a n =?=??≠? 5.15 知数列{k a }的指数生成函数是2()5x x G x x e =+,求k a 。

22

0()5252!!

k x

x k x x G x x e k ∞==+=+∑

72

52k k a k =?=?

≠?

6.5 平面上有n 条直线,它们两两相交且沿有三线交于一点,设这n 条直线把平面分成()f n 个区域,求()f n 的递推关系并求解.

解:设n-1条直线把平面分成(-1)f n 个区域,则第n 条直线与前n-1条直线都有一个交点,即在第n 条直线上有n-1个交点,并将其分成n 段,这n 段又把其所在的区域一分为二。

0101#11()(1),(2) (1)2 10 1 *()()12

(1)()2

1(1) ()12

f n f n n n f x x f n b b n n b b n n

f n c c n n f n =-+≥?∴?

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

=+∴=+

齐次特征方程:特征根:非齐次特解:代入递推关系得:,

代入递推关系得:

6.6 一个1n ?的方格图形用红、蓝两色涂色每个方格,如果每个方格只能涂一种颜色,且不允许两个红格相邻,设()f n 有种涂色方案,求()f n 的递推关系并求解.

解:

设f (n )为n ?1的方格图形的涂色方案。

当n=1时,f (1)=2,即一个方格有红、蓝两种涂色方案。 当n=2时,f (2)=3,即两个方格有(红、蓝),(蓝、红)、(蓝、蓝)三种涂色方案。由于不允许两个红格相邻,所以不存在(红、红)的情况。

当n>2时,如果第一个格子涂为蓝色,则剩余n-1个格子的涂色方案数为f (n -1);如果第一个格子涂为红色,由于不允许两个红格相邻,所以第二个格子必为蓝色,则剩余n-2个格子的涂色方案数为f (n -2)。于是,当n>2时涂色方案数为f (n )= f (n -1)+ f (n -2)。

(1)2;(2)3;

() (-1) (-2).

f f f n f n f n ==??

=+? 先求解这个递推关系的通解,它的特征方程为

,012=--x x

解这个方程,得

.2

5

1,25121-=+=

x x

所以,通解为

.251251)(21n

n c c n f ???

? ??-+???? ??+= 代入初值来确定1c 和2c ,得

12122,3 3.

22

=??+=?? 求解这个方程组,得

21,c =

?

?2

2.c =??

所以,原递推关系的解为

3

3

11()22n n f n ++??=??

( ,2,1,0=n ).

6.7 核反应堆中有α和β两种粒子,每秒钟内1个α粒子可反应产生出3个β粒子,而1个β粒子又可反应产生出1个α粒子和2个β粒子.若在t =0s 时刻反应堆中只有1个α粒子,求t =100s 时刻反应堆里将有多少个α粒子和β粒子.

解:

设t 时刻反应堆中α粒子数为()f t ,β粒子数为()g t

212#1212()(1),(2)()3(1)2(1)(0)1,(0)0()3(2)2(1),(2)(0)0,(1)3 230 3,1

()3(1)3344

3 ()34t t

f t

g t n g t f t g t f g g t g t g t n g g x x x x g t c c c c g t =-≥??

=-+-??==?

=-+-≥??

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

∴=?齐次特征方程:特征根:齐次通解:代入递推关系得:

,t 11

3

(1)43333 ()3(1)(1)4444

t t

t t t f t ---?-∴=?-?-=+?-

6.8 求下列n 阶行列式的值n d

21000

121000

1

2

000012

n d =?

解:当n=1时,122d == 当n=2时,221

312

d =

= 当n>2时,-1-22n n n d d d =-

先求解这个递推关系的通解,它的特征方程为

2210,x x -+=

解这个方程,得

121.x x ==

所以,通解为

12()1 1.

n n f n c c n =+?

代入初值来确定1c 和2c ,得 1212

2,

2 3.c c c c +=??

+=?

求解这个方程组,得 11,c =21.c = 所以,原递推关系的解为

()1f n n =+ ( ,2,1,0=n ).

6.9设h(n)表示n+2条边的凸多边形为它的对角线划分所得的区域数,其中假定没有二条对角线在凸多边形内有一公共点。定义h(0)=0,对n=l ,2,…,证明

1()(1)3n h n h n n +??

=-++ ???

证明:

如图所示,在凸n+2边形中,划出以任意两相邻边为边的三角形,例如△ABC 。则余下的是n+1个顶点的凸多边形,它的对角线划分所得的区域数为h(n-1)。由A 点引出的对角线共有n-1条,分△ABC 为n 块。下面我们计算一下由A 点引出的对角线对n+1条边的凸多边形划分所增加的区域数。

在n+1个顶点中仟取三个,不妨设为D ,F ,H ,其中必有一个顶点(这里是F)使得对角线AF 把D 和H 分在两边。所以对角线DH 必与对角线AF 相交。又由题意知,这个交点不会有其它对角线通过。这说明每新增加一个交点必与n+1个顶点中的三个顶点相对应。故新增加的交点数为C(n+1,3)个。

另外,从A 引出的每一条对角线上的交点数正好与这条对角线在凸n+1边形内截成的线段数相同,而每一线段恰好把n+1边形内某一区域分为两个,故新增加区域数为C(n+1,3)个。所以有

1()(1)3n h n h n n +??

=-++ ???

这是一个线性常系数非齐次递推关系,可以求得

2(1)()42n n n h n +??

+=

+ ???

(完整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.2. 求在1000和9999之间各位数字都不相同,而且由奇数构成的整数个数。 解:由奇数构成的4位数只能是由1,3,5,7,9这5个数字构成,又要求各位数字都不相同,因此这是一组从5个不同元素中选4个的排列,所以,所求个数为:P(5,4)=120。 1.4. 10个人坐在一排看戏有多少种就坐方式?如果其中有两人不愿坐在一起,问有多少种就坐方式? 解:这显然是一组10个人的全排列问题,故共有10!种就坐方式。如果两个人坐在一起,则可把这两个人捆绑在一起,如是问题就变成9个人的全排列,共有9!种就坐方式。而这两个人相捆绑的方式又有2种(甲在乙的左面或右面)。故两人坐在一起的方式数共有2*9!,于是两人不坐在一 起的方式共有 10!- 2*9!。 1.5. 10个人围圆桌而坐,其中两人不愿坐在一起,问有多少种就坐方式? 解:这是一组圆排列问题,10个人围圆就坐共有10 ! 10 种方式。 两人坐在一起的方式数为9 ! 92? ,故两人不坐在一起的方式数为:9!-2*8!。 1.14. 求1到10000中,有多少正数,它的数字之和等于5?又有多少数字之和小于5的整数? 解:(1)在1到9999中考虑,不是4位数的整数前面补足0, 例如235写成0235,则问题就变为求: x 1+x 2+x 3+x 4=5 的非负整数解的个数,故有 F (4,5)=??? ? ??-+=515456 (2)分为求: x 1+x 2+x 3+x 4=4 的非负整数解,其个数为F (4,4)=35 x 1+x 2+x 3+x 4=3 的非负整数解,其个数为F (4,3)=20 x 1+x 2+x 3+x 4=2 的非负整数解,其个数为F (4,2)=10 x 1+x 2+x 3+x 4=1 的非负整数解,其个数为F (4,1)=4 x 1+x 2+x 3+x 4=0 的非负整数解,其个数为F (4,0)=1 将它们相加即得, F (4,4)+F (4,3)+F (4,2)+F (4,1)+F (4,0)=70。 第二章: 2.3. 在边长为1的正三角形内任意放置5个点,则其中至少有两个点的距离≤1/2。 解:将边为1的正三角形分成边是为1/2的四个小正三角形,将5个点放入四个小正三角形中,由鸽笼原理知,至少有一个小正三角形中放有2个点,而这两点的距离≤1/2。 1/2 1/2 1/2

组合数学课后答案

作业习题答案 习题二 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.证:对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个点。

组合数学课后标准答案

组合数学课后标准答案

————————————————————————————————作者:————————————————————————————————日期:

习题二证明:在一个至少有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个坐标为整数的点,则其中至少有两个点,由它们所连线段的中点的坐标也是整数。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.题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个排好的元素,

组合数学题目及标准答案

组合数学 例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 必定是偶数。 例4 从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

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

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

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

组合数学 课后答案

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

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

第二章 容斥原理与鸽巢原理 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.

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

第四章 生成函数 1. 求下列数列的生成函数: (1){0,1,16,81,…,n 4,…} 解:G{k 4 }= 235 (11111) 1x x x x x +++-() (2)343,,,333n +?????????? ? ? ????? ???? 解:3n G n +?????? ?? ???=41(1)x - (3){1,0,2,0,3,0,4,0,……} 解:A(x)=1+2x 2+3x 4+4x 6+…=(2 11x -)2 . (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 -=0k 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.1 题 从{1,2,……50}中找两个数{a ,b},使其满足 (1)|a-b|=5; (2)|a-b|≤5; 解:(1):由|a-b|=5?a-b=5或者a-b=-5, 由列举法得出,当a-b=5时,两数的序列为(6,1)(7,2)……(50,45),共有45对。 当a-b=-5时,两数的序列为(1,6),(2,7)……(45,50)也有45对。 所以这样的序列有90对。 (2):由题意知,|a-b|≤5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0; 由上题知当|a-b|=5时 有90对序列。 当|a-b|=1时两数的序列有(1,2),(3,4),(2,1)(1,2)…(49,50),(50,49)这样的序列有49*2=98对。 当此类推当|a-b|=2,序列有48*2=96对,当|a-b|=3时,序列有47*2=94对,当|a-b|=4时,序列有46*2=92对, 当|a-b|=0时有50对 所以总的序列数=90+98+96+94+92+50=520 1.2题 5个女生,7个男生进行排列,(a) 若女生在一起有多少种不同的排列?(b) 女生两两不相邻有多少种不同的排列?(c) 两男生A 和B 之间正好有3个女生的排列是多少? 解:(a )可将5个女生看作一个单位,共八个单位进行全排列得到排列数为:8!×5!, (b )用x 表示男生,y 表示空缺,先将男生放置好,共有8个空缺, Y X Y X Y X Y X Y X Y X Y X Y 在其中任取5个得到女生两两不相邻的排列数: C (8,5)×7!×5! (c )先取两个男生和3个女生做排列,情况如下: 6. 若A ,B 之间存在0个男生, A ,B 之间共有3个人,所有的排列应为 P6=C(5,3)*3!*8!*2 1.若A ,B 之间存在1个男生, A ,B 之间共有4个人,所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2.若A ,B 之间存在2个男生,A ,B 之间共有5个人,所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3.若A ,B 之间存在3个男生,A ,B 之间共有6个人,所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4.若A ,B 之间存在4个男生,A ,B 之间共有7个人,所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*2 5.若A ,B 之间存在5个男生,A ,B 之间共有8个人,所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2 所以总的排列数为上述6种情况之和。 1.3题 m 个男生,n 个女生,排成一行,其中m,n 都是正整数,若 (a)男生不相邻)1(+≤n m ; (b)n 个女生形成一个整体; (c)男生A 和女生B 排在一起; 分别讨论有多少种方案。 解:(a) 可以考虑插空的方法。 n 个女生先排成一排,形成n+1个空。因为1+≤n m 正好m 个男生可以插在n+1个空中,形成不相邻的关系。 则男生不相邻的排列个数为 p p n m n n 1+? (b) n 个女生形成一个整体有n !种可能,把它看作一个整体和m 个男生排在一起,则排列数有(m+1)!种可能。 因此,共有)!1(!+?m n 种可能。 (c)男生A 和女生B 排在一起,因为男生和女生可以交换位置,因此有2!种可能, A 、B 组合在一起和剩下的学生组成排列有(m+n-1)! (这里实际上是m+n-2个学生和AB 的组合形成的)种可能。共有组合数为)!1(!2-+?n m 1.4题 26个英文字母进行排列,求x 和y 之间有5个字母的排列数 解:C (24,5)*13! 1.5题 求3000到8000之间的奇整数的数目,而且没有相同的数字。 解:根据题意,千位可以从3,4,5,7,6中选取,个位可以从1,3,5,7,9中选取;因此 2*5*8*7+3*4*8*7=1232 1.6 题 计算,1·1!+2·2!+3·3!+。。。+n·n ! 解:由序数法公式可知 1!+1=2! 2·2!+1·1!+1=3! 3·3!+2·2!+1·1!+1=4! n·n!+(n-1)(n-1)!+。。。+2·2!+1·1!+1= (n+1)! 所以1·1!+2·2!+3·3!+。。。+n·n !=(n+1)!-1 1.7题 试证:)2()2)(1(n n n ++被2n 除尽。 证明:因!)!12(!2)!2(-=n n n n !)!12(2 !)! 2(2!)2()2)(1(!2)2()2)(1(-==++=++n n n n n n n n n n n n n n 因为(2n-1)!!是整数所以)2()2)(1(n n n ++能被2n 除尽。

排列组合练习题及答案

排列组合习题精选 一、纯排列与组合问题: 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个 答案:1、2936C = 2、2972A = 3、选 B. 设男生n 人,则有2138390n n C C A -=。4、22 58m n m A A +-= 选C. 二、相邻问题: 1. A 、B 、C 、D 、E 五个人并排站成一列,若A 、B 必相邻,则有多少种不同排法? 2. 有8本不同的书, 其中3本不同的科技书,2本不同的文艺书,3本不同的体育书,将这些书竖排在书架上,则科技书连在一起,文艺书也连在一起的不同排法种数为( ) A.720 B.1440 C.2880 D.3600 答案:1.242448A A = (2) 选B 3253251440A A A = 三、不相邻问题: 1.要排一个有4个歌唱节目和3个舞蹈节目的演出节目单,任何两个舞蹈节目都不相邻,有多少种不同排法? 2、1到7七个自然数组成一个没有重复数字的七位数,其中奇数不相邻的有多少个? 3.4名男生和4名女生站成一排,若要求男女相间,则不同的排法数有( )

排列组合练习题及.答案

《排列组合》 一、排列与组合 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门,组成一个综合高考科目组,若要求这组科目中

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

第五章 P ólya 计数理论 1. 计算(123)(234)(5)(14)(23),并指出它的共轭类. 解:题中出现了5个不同的元素:分别是:1,2,3,4,5。即|S n |=5。 ??? ? ?????? ?????? ??=512345432152431543215413254321) 23)(14)(5)(234)(123( ??? ? ?????? ??=51234543215214354321 ??? ? ??=5341254321 )5)(34)(12(= (5)(12)(34)的置换的型为1122而S n 中属于1122型的元素个数为15 21!1!2! 52 1=个其共轭类为 (5)(14)(23),(5)(13)(24),(1)(23)(45),(1)(24)(35), (1)(25)(34),(2)(13)(45),(2)(14)(35),(2)(15)(34), (3)(12)(45),(3)(14)(25),(3)(15)(24),(4)(12)(35), (4)(13)(25),(4)(15)(24) 2. 设D 是n 元集合,G 是D 上的置换群.对于D 的子集A 和B ,如果存在G ∈σ, 使得}|)({A a a B ∈=σ,则称A 与B 是等价的.求G 的等价类的个数. 解:根据Burnside 引理∑= =n i i a c G l 1 1)(1,其中c 1(a i )表示在置换a i 作用下保持不变的元素个数,则有 c 1(σI )=n; 设在σ的作用下,A 的元素在B 中的个数为i ,则 c 2(σ)=n -2i ; 若没有其他置换,则G 诱出来的等价类个数为l=i n i n n -=-+)]2([2 1 3. 由0,1,6,8,9组成的n 位数,如果把一个数调转过来读得到另一个数,则称这两 个数是相等的.例如,0168和8910,0890与0680是相等的.问不相等的n 位数有多少个? 解:该题可理解为相当于n 位数,0,1,6,8,9这5个数存在一定的置换关系

相关主题
相关文档 最新文档