组合数学之容斥原理.ppt

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

1、组合数学容斥原理1一.引言●容斥原理所研究的问题是与若干有限集的交、并或差有关的计数.●在实际中,有时要计算具有某种性质的元素个数.例如:某单位举办一个外语培训班,开设英语,法语两门课.2●设U为该单位所有人集合,A,B分别为学英语,法语人的集合,如图所示.●学两门外语的人数为

2、AB

3、,只学一门外语的人数为

4、AB

5、-

6、AB

7、,没有参加学习的人数为

8、U

9、-

10、AB

11、.3在一些计数问题中,经常遇到间接计算一个集合中具有某种性质的元素个数比起直接计算来得简单.例如:计算1到700之间不能被7整除的整数个数.先计算1到700之间能被7整除的整数个数=700/7=100,所以1到70

12、0之间不能被7整除的整数个数=700-100=600.4上面举的间接计数的例子是利用了如下原理：如果A是集合S的子集,则A中的元素个数等于S中的元素个数减去不在A中的元素个数,这个原理可写成：5●原理的重要推广,称之为容斥原理,并且将它运用到若干问题上去,其中包括：错位排列、有限制的排列、禁位排列和棋阵多项式等.6DeMorgan定理:设A,B为全集U的任意两个子集,则DeMorgan定理的推广:设A1,A2,,An为U的子集,则二.容斥原理7证明从略abaUbaUb=a∩ba=u-a=b-aUbb=u-b=a-aUbb-aUb∩a-aUb=u-aUb=aUb81.两个集合的容

13、斥原理设A和B是分别具有性质P1和P2的元素的集合,则例6.1求1到500之间能被5或7整除的正整数个数.解设A为被5整除的整数集合,B为被7整除的整数集合,用[x]表示x的整数部分,则有9同时被5和7整除的整数个数故能被5或7整除的整数个数102.三个集合上的容斥原理设A,B,C为任意三个集合,则有3.n个集合上的容斥原理:设A1,A2,,An是有限集合,则有114.集合n中不具有a1,a2,a3…之一元素的个数为（余集形式）12例求在1到10000的整数中不能被4,5,6任意一个整除的数的个数.解：令Ai(i=4,5,6)表示1到10000的整数中能被i整除的数的个数，则1

14、3三.容斥原理的应用实例1.错排问题利用容斥原理很容易理解错排数列通项公式的组合意义.14（1..n）的错位排列个数记为Dn.结论如下：可以用容斥原理证明:设S={1,2,3,,n}的集合,S0为S的全排列，则s0=n!.令Aj表示排列1,2n中使j位置上的元素恰好是j的排列的集合,j=1,2,,n.则排列12n的所有错位排列组成集合:15Aj=(n-1)!,j=1,2,3,,n.AiAj=(n-2)!,i,j=1,2,3,,n,但ij.对于任意整数k且1kn,则有因为{1,2,3,,n}的k组合为C(n,k)个,应用容斥原理得到:1617课堂思考题

15、-被毁坏的玉米地问题描述：“哈姆！外星人又在那了！”。埃塞和哈姆他们的玉米地是长方形的。每年在丰收之前,他们的玉米地都会很奇怪地遭到毁坏（据埃塞说是外星人干的）。所有破坏的地方都是以1米为半径的圆。哈姆发现,如果在玉米地上建立一个适当的直角坐标系的话,那些圆心的坐标将都为整数。万幸的是,埃塞和哈姆有玉米保险,但必须把损坏的面积统计出来。输入文件（CROP.IN）:输入文件的第一行为一个整数N(O

16、4位。(Pi=3.1415926535)输入输出样例：CROP.IN20010CROP.OUT5.054818选做题：孪生项链19