《容斥原理初步》由会员分享，可在线阅读，更多相关《容斥原理初步（55页珍藏版）》请在金锄头文库上搜索。
1、第三章 容斥原理与鸽巢原理马昱春 12第三章 容斥原理与鸽巢原理ABAB容斥原理 Inclusion and Exclusion Principle 计数时重叠部分不能被重复计算 若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。 容斥的计数思想是: 先不考虑重叠的情况，把包含于某内容中的 所有对象的数目先计算出来； 然后再把计数时重复计算的数目排斥出去； 使得计算的结果既无遗漏又无重复。 33.1 容斥原理引论例 1，20中2或3的倍数的个数解 2的倍数是：2，4，6，8，10，12，14，16，18，20。 10个3的倍数是：3，6，9，12，15，
2、18。 6个但答案不是10+6=16 个，因为6，12，18 在两类中重复计数，应减去。故答案是：16-3=134 若A和B是集合U的子集，补集complement 德摩根De Morgan定理(a)(b)3.1 容斥原理引论U BA5证：(a)的证明。 设 ,则 相当于 和 同时成立，亦即 (1)反之，若故 (2)由（1）和（2）得(b)的证明和(a)类似，从略.(a)63.1 容斥原理引论DeMogan定理的推广：设A1,A2, . An是U的子集,证:采用数学归纳法正确即定理对n+1也是正确的。73.2 容斥原理最简单的计数问题是求有限集合A和B的并的元素数目。 (1)证 若AB=，则
3、| AB |= |A| + |B| | A | A ( BB) | (AB)(AB)| AB | + | AB | ( 1 ) 同理 | B | | BA | + | BA | ( 2 ) | AB |(A( BB)(B(AA)| |(AB)(AB)(BA)(BA)| | AB| + |AB | + | BA| ( 3 ) (3)-(2)-(1) 得到| AB | A | B | | AB| + |AB | + | BA| ( | AB | + | AB | )( | BA | + | BA | ) | AB | AB | A | + | B | AB |83.2 容斥原理定理：(2)93.2
4、 容斥原理103.2 容斥原理进一步可推出：11 定理设C(n,k)是1,n的所有k-子集的集合, 则证: 分析C(n,k)，可根据包含不包含n划分成两部分包含n的可看做C(n-1,k-1)中每个子集再加上元素n；不包含n的由C(n-1,k)组成；对n用归纳法。n=2时，等式成立。假设对n - 1，等式成立。对于n有C(2,k) = 1 2 k=1时1 2 k=2时C(3,k) = 1 2 3 k=1时1 21 32 3 k=2时1 2 3 k=3时k2C(3,2) = 1 32 31 212 证由于最后一项第一项133.2 容斥原理 此定理也可表示为：(4)143.2 容斥原理其中N是集合U
5、的元素个数，即不属于A的元素 个数等于集合的全体减去属于A的元素的个数 。一般有：(5)15Inclusion-Exclusion Principle计算不在 A1 也不在 A2中的元素个数若x不属于A1 或A211-0-0+0 = 1 若x 属于A1 但不属于A20 1-1-0+0 = 0若x 属于A2 但不属于A10 1-0-1+0 = 0 若x 属于A2 且属于A10 1-1-1+1 = 0两边相等16计算不满足任意属性的元素.x不满足任何属性11-0-0+(-1)m0 = 1 x只满足1个属性0 1-1-0 +(-1)m0 = 0x只满足n个属性, nm0C(n,0)-C(n,1)+C
6、(n,2)+(-1)mC(n,m) = C(n,0)-C(n,1)+C(n,2)+(-1)nC(n,n) +0 +0 =0 两边相等，同样计算不满足任何属性的元素个数(x+y)m =C(m,0)xm+ C(m,1)xm-1y+C(m,m)ym If x=1, y=-1 0 = C(m,0)- C(m,1) +(-1)mC(m,m)173.2 容斥原理 容斥原理指的就是（4）和（5）式。(4)(5) Inclusionexclusion principle This concept is attributed to Abraham de Moivre (1718) It first appear
7、s in a paper of Daniel da Silva (1854) Later in a paper by J. J. Sylvester (1883) “One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusionexclusion. When skillfully applied, this principle has yielded the solution to
8、many a combinatorial problem.“ 193.2 容斥原理例 一个学校只有三门课程：数学、物理、化学。已知修这三门 课的学生分别有170、130、120人；同时修数学、物理两门课的 学生45人；同时修数学、化学的20人；同时修物理化学的22人。 同时修三门的3人。问这学校共有多少学生？ 令：M为修数学的学生集合；P 为修物理的学生集合；C 为修化学的学生集合；即学校学生数为336人。203.3 举例例1 求a,b,c,d,e,f六个字母的全排列中不允许出现 ace和df图象的排列数。 解：6个字母全排列： |S| = 6! 设A为ace作为一个元素出现的排列集: |A|
9、=4!，B为 df作为一个元素出现的排列集: |B|=5!， AB为同时出现ace、df的排列数: |AB |=3!。213.3 举例例2 求从1到500的整数中能被3或5除尽的数的个数。解： 令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合被3或5除尽的数的个数为223.3 举例例3 求由a,b,c,d四个字母构成的n位符号串中，a,b,c都 至少出现一次的符号串数目。解：令A、B、C分别为n位符号串中不出现a，b，c符号的集 合。由于n位符号串中每一位都可取a，b，c，d四种符号中的一 个，故不允许出现a的n位符号串的个数应是3n个，即：a，b，c至少出现一次的n位符号
10、串集合即为233.3 举例例5。用26个英文字母作不允许重复的全排列，要求排除dog， god，gum，depth，thing字样的出现，求满足这些条件的排列数。解：令A1为出现dog，| A1 |=24！令A2为出现god，| A2 |=24！令A3为出现gum，| A3 |=24！令A4为出现depth，| A4 |=22！令A5为出现thing，| A5 |=22！ | A1A2| = 0, A1A3, dogum: | A1A3| = 22!, A2A4, godepth: | A2A4| = 20!, A2A5, thingod: | A2A5| = 20!, A3A4, gum*d
11、epth或者gum*depth : | A3A4| = 20！ A3A5, thingum: | A3A5| = 20！ A4A5, depthing: | A4A5| = 19!, A1A3 A4,dogumdepth 0; A2A4 A5, godepthing 0; A3A4 A5, depthingum | A3A4 A5 | = 17！ 所求的排列数为 26!-(3*24!+2*22!)+(22!+4*20!+19!)-(17!)243.3 举例0 00 11 01 1f(x1,x2) f10000 f20001 f30010 f40011 f50100 f60101 f70110
12、f80111 f91000 f101001 f111010 f121011 f131100 f141101 f151110 f161111例6。求完全由n个布尔变量确定的布尔函数的个数。f(x1,x2,xn)中n个 布尔变量的不同的 状态数为2n 每个状态有0，1两 种取值， 故f(x1,x2,xn)的布 尔函数个数为 25例6。求完全由n个布尔变量确定的布尔函数的个数。 解：设布尔函数类为：有1个变量不出现的布尔函数个数为 有2个变量不出现的布尔函数个数为 有k个变量不出现的布尔函数个数为 根据容斥原理，满足条件的函数数目为：f(x1,x2,xn)的布尔函数个数为263.3 举例0 00 1
13、1 01 1f(x1,x2) f10000 f20001 f30010 f40011 f50100 f60101 f70110 f80111 f91000 f101001 f111010 f121011 f131100 f141101 f151110 f161111例6。求完全由n个布尔变量确定的布尔函数的个数。f(x1,x2,xn)中n个 布尔变量的不同的 状态数为2n 每个状态有0，1两 种取值， 故f(x1,x2,xn)的布 尔函数个数为 273.3 举例 例4。求不超过120的素数个数。 因112=121，故不超过120的合数必然是2、3、5、7的 倍数，而且不超过120的合数的因子不
14、可能都超过11。 设Ai为不超过120的数 i的倍数集， i=2，3，5，7。28注意：因为27个数中排除了 2，3，5，7四个素数，又 包含了1这个非素数。故所 求的不超过120的素数个数 为：27+4-1=3029例7。欧拉函数(n)是求小于n且与n互素的数的个数。 分析的化身 欧拉进行计算看起来毫不费劲儿，就像人进行呼吸，像鹰在风中 盘旋一样。 他是历史上最多产的数学家。 彼得堡学院为了整理他的著作整整花了47年。 欧拉确实常常在两次叫他吃晚饭的半小时左右的时间里赶出一篇 数学论文 欧拉是史上发表论文数第二多的数学家，全集共计75卷；他的纪 录一直到了20世纪才被保羅埃尔德什打破 “读欧拉的著作吧，在任何意义上，他都是我们的大师” 人生波折：失明，火灾 1783年9月18日，他77岁的时候，欧拉写出了他对天王星轨道的 计算。他在喝着茶跟孩子玩的时候，中风发作。手中烟斗掉了， 只说出一句话“我要死了“,“欧拉便停止了生命和计算。“在计算机领域中广泛使用的RSA公钥密码 算法也正是以欧拉函数为基础的。-拉普拉斯303.3 举例例7。欧拉函数(n)是求小于n且与n互素的数的个数。 解：若n分解为不同素数的乘积设1到n的n个数中为pi倍数的集合为Ai(8)=4 8 = 23，小于8且与
