ch3 容斥原理 (组合数学).ppt

《ch3 容斥原理 (组合数学).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对于组合性质的事物，常遇到计数问题。前一章，我们学习了如何用母函数去进行计数。除母函数方法外，还有两个特别的计数工具----容斥原理和PÓlya计数定理。本章我们先学习容斥原理及其应用。为此，先从几个简单例子说起。3.1容斥原理[解]2的倍数是：2，4，6，8，10，12，14，16，18，20。共10个；3.1容斥原理例1，求[1，20]中2或3的倍数的数的个数.否！因为6，12，18在两类中重复计数，应减去。3的倍数是：3，6，9，12，15，18。共6个；答案是10+6=16个吗？故答案是：16-3=13容斥原理研究有限集合的交或并的计数。则有3.1容斥原理(

2、b)[DeMorgan定理]论域U，A的补集(a)(1)3.1容斥原理证：(a)的证明相当于和同时成立，亦即若则反之，若故(2)由（1）和（2）得(b)的证明和(a)类似，从略.3.1容斥原理DeMogan定理的推广：证明：只证(a).n=2时，定理已证。设定理对n是正确的，即假定：3.1容斥原理设正确即定理对n+1也是正确的。3.1容斥原理最简单的计数问题是求有限集合A和B的并的元素数目。显然有即具有性质A或B的元素的个数等于具有性质A的元素个数和具有性质B的元素个数减去同时具有性质A和B的元素个数。(1)定理13.1容斥原理UBA3.1容斥原理3.1容斥原理证若

3、A∩B=φ，则

4、A∪B

5、=

6、A

7、+

8、B

9、,否则同理

10、B

11、＝

12、B∩A

13、+

14、B∩A

15、(2)

16、A

17、＝

18、A∩(B∪B)

19、＝

20、(A∩B)∪(A∩B)

21、＝

22、A∩B

23、+

24、A∩B

25、(1)3.1容斥原理

26、A∪B

27、－

28、A

29、－

30、B

31、＝

32、A∩B

33、+

34、A∩B

35、+

36、B∩A

37、－(

38、A∩B

39、+

40、A∩B

41、)－(

42、B∩A

43、+

44、B∩A

45、)＝－

46、A∩B

47、(3)－(1)－(2)得∴

48、A∪B

49、＝

50、A

51、+

52、B

53、－

54、A∩B

55、3.1容斥原理证明定理23.1容斥原理3.1容斥原理ABC例2,一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；

56、同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？3.1容斥原理解：令M为修数学的学生集合；P为修物理的学生集合；C为修化学的学生集合；则即学校学生数为336人。3.1容斥原理同理可推出：利用数学归纳法可得一般的定理：3.1容斥原理3.1容斥原理证对n用归纳法。n=2时，等式成立。假设对n-1，等式成立。对于n有定理3设(n,k)是［1,n］的所有k-子集的集合,则3.1容斥原理3.1容斥原理(4)定理3’设是有限集合，则此定理也可表示为：其中N是集合U的元素个数.即不属于A的元素个数等于集合的全体减去属于A的元素的个数.一

57、般有:3.1容斥原理(5)容斥原理指的就是（4）和（5）式。解：设A为ace作为一个元素出现的排列集，B为df作为一个元素出现的排列集,AB为同时出现ace、df的排列数。3.1容斥原理例3求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。根据容斥原理，不出现ace和df的排列数为：=6!-(5!+4!)+3!=582例4求从1到500的整数中能被3或5除尽的数的个数.3.1容斥原理解：令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合被3或5除尽的数的个数为解：令A、B、C分别为n位符号串中不出现a，b，c符号的集合

58、。由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是3^n即有3.1容斥原理例5求由a,b,c,d四个字母构成的位符号串中,a,b,c,d至少出现一次的符号串数目。a,b,c至少出现一次的n位符号串集合即为3.1容斥原理例6，求不超过120的素数个数。因11×11=121，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。设Ai为不超过120的数i的倍数集，i=2,3,5,7。3.1容斥原理3.1容斥原理3.1容斥原理3.1容斥原理3.1容斥原理注意：27并非就是不超过120的

59、素数个数，因为这里排除了2,3,5,7着四个数,又包含了1这个非素数。2,3,5,7本身是素数.故所求的不超过120的素数个数为：27+4-1=30例7，用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。3.1容斥原理解：所有排列中，令出现dog字样的排列，相当于把dog作为一个单元参加排列，故类似有：由于god,dog不可能在一个排列中同时出，故：类似：3.1容斥原理由于gum,dog可以在dogum字样中同时出现，故有：类似有god和depth可以在godepth字样中同时出现，故