组合数学 第3章-作业参考解答学习资料.doc

第3章容斥原理与鸽巢原理

作业题参考解答

3.2求从1到500的整数中被3和5整除但不被7整除的数的个数.

[解]??设A3：被3整除的数的集合

A5：被5整除的数的集合

A7：被7整除的数的集合

所以：

3.12一年级有100名学生参加中文，英语和数学的考试，其中92人通过中文考试，75人通过英语考试，65人通过数学考试；其中65人通过中，英文考试，54人通过中文和数学考试，45人通过英语和数学考试，试求通过3门学科考试的学生数。

[解]令A1为通过中文考试的学生人数

A2为通过英语考试的学生人数

A3为通过数学考试的学生人数

于是|A1|=92，|A2|=75，|A3|=65

|A1∩A2|=65，|A1∩A3|=54，|A2∩A3|=45

至少有92人通过三门中至少一门考试，即

至多有8人没通过一门考试，即0≤|∩∩|≤8

根据容斥原理，有

|A1∪A2∪A3|=(|A1|+|A2|+|A3|)-(|A1∩A2|+|A1∩A3|+|A2∩A3|)+|A1∩A2∩A3|

即|A1∩A2∩A3|=|A1∪A2∪A3|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A2∩A3|)

=|A1∪A2∪A3|-(92+75+65)+(65+54+45)

=|A1∪A2∪A3|-232+164

=|A1∪A2∪A3|-68

由得：24≤|A1∩A2∩A3|≤32

所以，通过3门学科考试的学生数在24到32人之间。

3．20在由a,a,a,b,b,b,c,c,c,组成的排列中，求满足下列条件的排列数，

（1）不存在相邻3元素相同；

（2）相邻两元素不相同。

[解]（1）令S为所有元素排成一列的排列数

为三个相邻的排列数

所以

根据容斥原理，有

（2）方法一：令Z={由a,a,a,b,b,b,c,c,c组成的全排列}。则|Z|=9!/(3!3!3!)=1680。

令A1={Z中出现图像aa的全排列}，A2={Z中出现图像bb的全排列}，

A3={Z中出现图像cc的全排列}。

因为将aa与a看做为不同的两个元素参与排列，在它们相遇之时会产生重复，其重复数刚好是将aaa看作一个整体参与排列的个数，因此有

|A1|=8!/(3!3!)－7!/(3!3!)=1120－140=980。

同理可得|A2|=|A3|=8!/(3!3!)－7!/(3!3!)=1120－140=980。

因为A1∩A2为aa,bb图象都出现的排列集合，当我们将aa与a,bb与b看作不同的两对元素进行排列时有排列数7!/3!，但这其中在aa与a相遇而成aaa图象，或bb与b相遇而成bbb图象时会产生重复计数，需要减去多算的：仅aa与a相遇而成aaa图象重复算了2次（多算了1次），仅bb与b相遇而成bbb图象重复算了2次（多算了1次），但aa与a相遇而成aaa图象且aa与a相遇而成aaa图象重复算了4次（多算了3次）。因此有

|A1∩A2|=7!/3!－(6!/3!－2*5!/3!)－(6!/3!－2*5!/3!)－3*5!/3!=620。

(注：6!/3!表示出现aaa图像的排列数（这其中包含同时也出现bbb的图像的排列数重复算了2次），因此上式的第一项6!/3!－2*5!/3!表示仅出现aaa图像而没有出现bbb图像的排列数；第二项6!/3!－2*5!/3!表示仅出现bbb图像而没有出现aaa图像的排列数；第三项5!/3!表示同时出现aaa和bbb图像的排列数。)

同理可得|A1∩A3|=620，|A2∩A3|=620。

|A1∩A2∩A3|=6!－7*3!－3[C(3,2)*(4!－2*3!)]－C(3,1)[5!-2*(4!-2*3!)-2*(4!-2*3!)-4*3!]=426。

(注1：在6!中要减去重复的计数：同时出现aaa、bbb、ccc图像的排列数3!算了8次，因此要减去7*3!；恰同时出现aaa、bbb、ccc图像之二的排列数C(3,2)(4!－2*3!)算了4次，因此要减去3[C(3,2)*(4!－2*3!)]；仅出现aaa、bbb、ccc图像之一的排列数C(3,1