鸽巢原理+容斥原理.ppt

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

1、容斥原理1容斥原理容斥原理（相容排斥原理）是组合计数中常用到的一种方法。例1求不超过20的正整数中是2的倍数或3的倍数的数的个数。不超过20的正整数中是2的倍数的数有10个，即2,4,6,8,10,12,14,16,18,20。不超过20的正整数中是3的倍数的数有6个，即3,6,9,12,15,18。但是不超过20的正整数中是2的倍数或3的倍数的数的个数不是10+6=16个，而是13个，因为其中6,12,18这三个数既是2的倍数又是3的倍数。2容斥原理集合论加法法则：若

2、A

3、=m，

4、B

5、=n，AB=，则

6、AB

7、=m+n。思考：若A、B为任意的有限集合，则

8、AB

9、=？3容斥原理定理1若A

10、、B为任意的有限集合，则4容斥原理例1求不超过20的正整数中是2的倍数或3的倍数的数的个数。解：设A、B分别表示不超过20的正整数中2的倍数的数的集合和3的倍数的数的集合，则问题转化为求

11、AB

12、易见

13、A

14、=10，

15、B

16、=6，

17、AB

18、=3因此

19、AB

20、=

21、A

22、+

23、B

24、-

25、AB

26、=135容斥原理定理2若A、B、C为任意的有限集合，则6容斥原理利用数学归纳法可获得容斥原理的一般形式：定理3设是有限集合，则7容斥原理容斥原理的等价形式：定理4设是有限集合，则8容斥原理例2一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人

27、；同时修数学、化学的20人；同时修物理、化学的22人。同时修三门的3人。问这学校共有多少学生？解令M、P、C分别为修数学、物理、化学的学生集合则该问题转化为求

28、MPC

29、9容斥原理例3求1~1000中不能被5、6和8中任何一数整除的整数的个数解：设1~1000之间的整数构成全集EA、B、C分别表示其中可被5，6，8整除的数的集合则问题转化为求

30、~A~B~C

31、由于ABC=1000/[5，6，8]=1000/120=8AB=1000/[5，6]=33AC=1000/[5，8]=25BC=1000/[6，8]=41A=1000/5=200

32、B=1000/6=166C=1000/8=12510容斥原理由ABC=8AB=33AC=25BC=41A=200B=166C=125所以由容斥原理，不能被5，6和8整除的整数的个数为

33、~A~B~C

34、=

35、E

36、-（A+B+C）+（AB+AC+BC）-ABC=60011容斥原理例4求a,b,c,d,e,f六个字母的全排列中不出现ace和df的排列数。解设E为全排列集合，A为出现ace的排列的集合，B为出现df的排列的集合，则根据容斥原理，不出现ace和df的排列数为12容斥原理在组合数学中的应用错排问题有禁

37、止模式的排列问题13错排问题错排问题是指对n个元素依次给以标号1,2,…,n，求每个元素都不在自己原来位置上的排列数。设Ai(i=1,2,…,n)为数i在第i位上的全体排列，因数字i不能动，因而有

38、Ai

39、=(n-1)!，i=1,2,…,n同理14错排问题定理用Dn表示{1,2,…,n}的全部错排个数，则15错排问题例在8个字母ABCDEFGH的全排列中，求（1）仅ACEG四个字母不在原来位置上的排列数（2）只有4个字母不在原来位置的排列数（3）ACEG四个字母不在原来上的排列数解（1）8个字母中仅ACEG四个字母不在原来位置上，其余4个字母保持不动，相当于4个元素的错排排列数为（2）排列数为C

40、(8,4)9=63016错排问题（3）8个字母的全排列中，令A1,A2,A3,A4分别表示A,C,E,G在原来位置上的排列则满足要求的排列为17有禁止模式的排列问题有禁止模式的排列问题主要解决某些元素之间的某种相对位置不能出现的一类排列。下面我们仅讨论有禁止模式的排列问题中最简单的一种——相邻禁位问题。18相邻禁位问题相邻禁位问题：求由集合{1,2,…,n}产生的不出现12,34,…,n(n-1)的全排列数设Qn表示{1,2,…,n}的不出现12,34,…,n(n-1)的全排列数则Q1=1，满足要求的排列为1；Q2=1，满足要求的排列为21；Q3=3，满足要求的排列为213,321,132；

41、Q4=11，满足要求的排列为：4132,3142,2143，1324,4213,3214,2413,1432,4321,3241,2431Qn=？19相邻禁位问题设S为{1,2,…,n}的所有全排列，则

42、S

43、=n!，设Ai（i=1,2,…,n-1）表示全排列中出现i(i+1)模式的排列的集合则Ai中的每一个排列都可看作n-1元集合{1,2,…,i(i+1),…,n}的一个全排列，所以

44、Ai

45、=(n