第9讲容斥原理

《第9讲容斥原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、应用组合数学第9讲容斥原理张坤龙zhangkl@tju.edu.cn目录集合N，n个属性•容斥原理–求具有n个属性之一（并集）的元素的个数–求不具有n个属性中任何一个（交集）的元素的个数•广义容斥原理–求恰好具有m个属性的元素的个数容斥原理•并集的计数•交集的计数•容斥原理的应用–有禁区的排列两个集合的并集U[定理1]AABIB

2、A∪B

3、=

4、A

5、+

6、B

7、-

8、A∩B

9、[例1]求不超过20的正整数中2或3的倍数的个数解：令A为2的倍数集合，B为3的倍数集合

10、A

11、==10⎣⎦20/2

12、B

13、==6

14、A⎣⎦20/3}∪B

15、=

16、A

17、+

18、B

19、-

20、A∩B

21、=13

22、A∩B

23、==3⎣⎦20/6三个

24、集合的并集U[定理2]AIB

25、A∪B∪C

26、=

27、A

28、+

29、B

30、+

31、C

32、AAIIBCB-

33、A∩B

34、-

35、A∩C

36、-

37、B∩C

38、AICBIC+

39、A∩B∩C

40、C[例2]一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学物理两门课的学生45人；同时修数学化学的20人；同时修物理化学的22人。同时修三门课程的3人。问这学校共有多少学生，假设每个学生至少修一门课？解:

41、M∪P∪C

42、=170+130+120-45-20-22+3=336多个集合的并集[定理3]设A,A,L,A是有限集合，则12nn

43、A1UUUA2LAn

44、=∑

45、Ai

46、i=1n−∑∑

47、

48、AiIAj

49、ii=>1jn+∑∑∑

50、AiIIAjAk

51、ii=>>1jjk−Ln−1+(−1)

52、A1IIA2LIAn

53、证明：数学归纳法DeMorgan定理[定理4]若A,B是U的子集，则AUB=AIBAIB=AUB[定理5]若A,A,…A是U的子集，则12nA1UUA2ULAn=A1IA2ILIAnA1IIA2ILAn=A1UA2ULUAnSylvester公式[定理6]给定集合N和具有性质i的集合A,A,L,A，则12nn

54、A1IA2ILIAn

55、=

56、N

57、−∑

58、Ai

59、i=1n+∑∑

60、AiIAj

61、ii=>1jn−∑∑∑

62、AiIIAjAk

63、ii=>>1jjk+Ln+(−1)

64、A1II

65、A2LIAn

66、有限制的排列[例3]求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。解：设A为ace作为一个元素出现的排列集，B为df作为一个元素出现的排列集，则

67、N

68、=6!⎫

69、A

70、=4!⎪⎬

71、AIB

72、=6!−(5!+4!)+3!=582

73、B

74、=5!⎪

75、A∩B

76、=3！⎭[例4]4个x、3个y、2个z的全排列中，求不出现xxxx、yyy、zz图象的排列数。解:所有出现xxxx图象的排列集合记为A，出现yyy图1象的排列集合记为A，出现zz图象的排列集合记为2A,则3

77、A1IA2IA3

78、=

79、N

80、−(

81、A1

82、+

83、A2

84、+

85、A3

86、)+(

87、A1IA2

88、+

89、A1

90、IA3

91、+

92、A2IA3

93、)−

94、A1IIA2A3

95、=P(9;4,3,2)−[P(6;1,3,2)+P(7;4,1,2)+P(8;4,3,1)]+[P(4;1,1,2)+P(5;1,3,1)+P(6;4,1,1)]-P(3;1,1,1)=1260-(60+105+280)+(12+20+30)-6=871Eratosthenes筛法[例5]求不超过120的素数的个数。解：不超过120的合数必然是2、3、5、7的倍数，且不超过120的合数的因子不可能都超过11。设Ai为不超过120的数i的倍数集，i=2，3，5，7。

96、A2IA3IA5IA7

97、=

98、N

99、−(

100、A

101、+

102、A

103、+

104、A

105、+

106、A

107、

108、)2357+(

109、A2IA3

110、+

111、A2IA5

112、+

113、A2IA7

114、+

115、A3IA5

116、+

117、A3IA7

118、+

119、A5IA7

120、)−(

121、A2IIA3A5

122、+

123、A2IIA3A7

124、+

125、A2IIA5A7

126、+

127、A3IIA5A7

128、)+

129、A2IIA3A5IA7

130、=120⎢120⎥⎢120⎥⎢120⎥⎢120⎥−(+++)⎢⎥⎢⎥⎢⎥⎢⎥⎣2⎦⎣3⎦⎣5⎦⎣7⎦⎢120⎥⎢120⎥⎢120⎥⎢120⎥⎢120⎥⎢120⎥+(+++++)⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣2×3⎦⎣2×5⎦⎣2×7⎦⎣3×5⎦⎣3×7⎦⎣5×7⎦⎢120⎥⎢120⎥⎢120⎥⎢120⎥−(+++)⎢⎥⎢⎥⎢⎥⎢⎥⎣2×3×5⎦⎣2×3×7

131、⎦⎣2×5×7⎦⎣3×5×7⎦⎢120⎥+=27⎢⎥⎣2×3×5×7⎦由于2，3，5，7是素数，1不是素数，故所求的不超过120的素数个数为：27+4-1=30欧拉函数φ(n)[例6]欧拉函数φ(n)是小于等于n且与n互素的正整数的个数,假设n=pα1pα2Lpαk,则有12k111φ(n)=n(1−)(1−)L(1−)ppp12k证明：设A为1到n之间p的倍数的集合,i=1,2,L,k,则iiφ(n)=

132、A1IA2ILIAk

133、kkknnnkn=n−∑+∑∑−∑∑∑+L+(−1)i=1pii