组合数学之容斥原理.ppt

一. 引言 ●设U为该单位所有人集合, A,B分别为 学英语, 法语人的集合, 如图所示. 在一些计数问题中, 经常遇到间接计算一个集合中具有某种性质的元素个数比起直接计算来得简单. 例如: 计算1到700之间不能被7整除的整数个数. 先计算1到700之间能被7整除的整数个数=700/ 7=100, 所以1到700之间不能被7整除的整数个数=700-100=600. 上面举的间接计数的例子是利用了如下原理：如果A是集合S的子集, 则A中的元素个数等于S中的元素个数减去不在A中的元素个数, 这个原理可写成： ● 原理的重要推广, 称之为容斥原理,并且将它运用到若干问题上去, 其中包括： 错位排列、 有限制的排列、 禁位排列和 棋阵多项式等. 二. 容斥原理 DeMorgan定理: 设A, B为全集U的任意 两个子集, 则 证明从略 1. 两个集合的容斥原理 设A和B是分别具有性质P1和P2的元素的集合, 则 同时被5和7整除的整数个数 2. 三个集合上的容斥原理 设A, B, C为任意三个集合, 则有 4. 集合n中不具有a1,a2,a3…之一元素的个数为（余集形式） 三. 容斥原理的应用实例 1. 错排问题 利用容斥原理很容易理解错排数列通项公式的组合意义. ?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米为半径的圆。哈姆发现,如果在玉米地上建立一个适当的直角坐标系的话,那些圆心的坐标将都为整数。万幸的是,埃塞和哈姆有玉米保险,但必须把损坏的面积统计出来。 输入文件（CROP.IN）: 输入文件的第一行为一个整数N(ON=200)，表示圆圈的个数。以下N行每行有两个整数x和y，由空格分开，代表圆心坐标。数据中不存在两个完全重合的圆。 输出文件（CROP.OUT）: 输出统计出的总面积，四舍五入到小数点后4位。(Pi = 3.1415926535) 输入输出样例： CROP.IN 2 0 0 1 0 CROP.OUT 5.0548 选做题：孪生项链 * * 组合数学 容斥原理 ●容斥原理所研究的问题是与若干有 限集的交、并或差有关的计数. ●在实际中, 有时要计算具有某种性质的元素个数. 例如: 某单位举办一个外语培训班, 开设 英语, 法语两门课. ●学两门外语的人数为|A?B|, 只学一门外语的人数为|A?B|-|A?B|, 没有参加学习的人数为|U|-|A?B|. DeMorgan定理的推广: 设A1,A2,?,An为 U的子集, 则 a b aUb aUb=a∩b a=u-a=b-aUb b=u-b=a-aUb b-aUb∩a-aUb =u-aUb=aUb 例6.1 求1到500之间能被5或7整除的正整数个数. 解 设A为被5整除的整数集合, B为被7整除的整数集合, 用[x]表示x的整数部分, 则有 故能被5或7整除的整数个数 3. n个集合上的容斥原理: 设A1,A2,?,An是有限集合, 则有 例求在1到10000的整数中不能被4,5,6任意一个整除的数的个数. 解：令Ai(i=4,5,6)表示1到10000的整数中能被i整 除的数的个数，则 （1..n）的错位排列个数记为Dn. 结论如下： 可以用容斥原理证明: 设S={1,2,3,?,n}的集合, S0为S的全排列，则s0=n! . 令Aj表示排列1,2?n中使j位置上的元素恰好是j的排列的集合, j=1,2,?,n. 则排列12?n的所有错位排列组成集合: 因为{1,2,3,?,n}的k组合为C(n,k)个, 应用容斥原理得到: