资源描述：
《卢开澄组合数学--组合数学第三章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章容斥原理和鸽巢原理§1容斥原理引论例[1，20]中2或3的倍数的个数[解]2的倍数是：2，4，6，8，10，12，14，16，18，20。10个§3.1容斥原理引论3的倍数是：3，6，9，12，15，18。6个但答案不是10+6=16个，因为6，12，18在两类中重复计数，应减去。故答案是：16-3=13§3.2容斥原理容斥原理研究有限集合的交或并的计数。[DeMorgan定理]论域U，补集,有§3.2容斥原理(a)(b)证：(a)的证明。设,则相当于和同时成立，亦即(1)§3.2容斥原理反之，若故(2)由（1）和（2）得(b)的证
2、明和（a)类似，从略.§3.2容斥原理DeMogan定理的推广：设证明：只证(a).N=2时定理已证。设定理对n是正确的，即假定：§3.2容斥原理正确即定理对n+1也是正确的。§3.2容斥原理§2容斥原理最简单的计数问题是求有限集合A和B的并的元素数目。显然有即具有性质A或B的元素的个数等于具(1)定理：§3.2容斥原理有性质A和B的元素个数。UBA§3.2容斥原理§3.2容斥原理证若A∩B=φ，则
3、A∪B
4、=
5、A
6、+
7、B
8、
9、A
10、＝
11、A∩(B∪B)
12、＝
13、(A∩B)∪(A∩B)
14、＝
15、A∩B
16、+
17、A∩B
18、(1)同理
19、B
20、＝
21、B∩A
22、+
23、B∩
24、A
25、(2)
26、A∪B
27、＝
28、(A∩(B∪B))∪(B∩(A∪A))
29、＝
30、(A∩B)∪(A∩B)∪(B∩A)∪(B∩A)
31、＝
32、A∩B
33、+
34、A∩B
35、+
36、B∩A
37、(3)§3.2容斥原理(3)－(1)－(2)得
38、A∪B
39、－
40、A
41、－
42、B
43、＝
44、A∩B
45、+
46、A∩B
47、+
48、B∩A
49、－(
50、A∩B
51、+
52、A∩B
53、)－(
54、B∩A
55、+
56、B∩A
57、)＝－
58、A∩B
59、∴
60、A∪B
61、＝
62、A
63、+
64、B
65、－
66、A∩B
67、定理：(2)§3.2容斥原理§3.2容斥原理ABC§3.2容斥原理例一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物
68、理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？§3.2容斥原理令：M为修数学的学生集合；P为修物理的学生集合；C为修化学的学生集合；§3.2容斥原理即学校学生数为336人。§3.2容斥原理同理可推出：利用数学归纳法可得一般的定理：§3.2容斥原理定理设￠(n,k)是［1,n］的所有k-子集的集合,则
69、∪Ai
70、=∑(－1)k-1∑
71、∩Ai
72、证对n用归纳法。n=2时，等式成立。假设对n-1，等式成立。对于n有§3.2容斥原理ni=1k=1nI∈￠(n,k)i∈I§3.2容斥原理
73、I∈￠(n-1,k)I∈￠(n-1,k)i∈I§3.2容斥原理I∈￠(n,k)I∈￠(n-1,k-1)I∈￠(n-1,k)此定理也可表示为：定理：设是有限集合，则(4)§3.2容斥原理证：用数学归纳法证明。已知n=2时有设n-1时成立，即有：§3.2容斥原理§3.2容斥原理§3.2容斥原理§3.2容斥原理§3.2容斥原理§3.2容斥原理§3.2容斥原理§3.2容斥原理其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于A的元素的个数。一般有：§3.2容斥原理(5)容斥原理指的就是（4）和（5）式。§3.2容斥原理§3例例1
74、求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。解：设A为ace作为一个元素出现的排列集，B为df作为一个元素出现的排列集，为同时出现ace、df的排列数。§3.3例根据容斥原理，不出现ace和df的排列数为：=6!-(5!+4!)+3!=582§3.3例例2求从1到500的整数中能被3或5除尽的数的个数。解：令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合§3.3例被3或5除尽的数的个数为例3求由a,b,c,d四个字母构成的位符号串中，a,b,c,d至少出现一次的符号串数目。§3.3例解
75、：令A、B、C分别为n位符号串中不出现a，b，c符号的集合。由于n位符号串中每一位都可取a，b，c，d四种符号中的一个，故不允许出现a的n位符号串的个数应是§3.3例a，b，c至少出现一次的n位符号串集合即为§3.3例例4。求不超过120的素数个数。因，故不超过120的合数必然是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。设为不超过120的数的倍数集，=2，3，5，7。§3.3例§3.3例§3.3例§3.3例§3.3例注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7着四个数，又包含了1这个非素
76、数。2，3，5，7本身是素数。故所求的不超过120的素数个数为：27+4-1=30§3.3例例5。用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字
