组合数学之容斥原理.pptVIP

1 组合数学 容斥原理 2 一 引言 容斥原理所研究的问题是与若干有限集的交 并或差有关的计数 在实际中 有时要计算具有某种性质的元素个数 例如 某单位举办一个外语培训班 开设英语 法语两门课 3 设U为该单位所有人集合 A B分别为学英语 法语人的集合 如图所示 学两门外语的人数为 A B 只学一门外语的人数为 A B A B 没有参加学习的人数为 U A B 4 在一些计数问题中 经常遇到间接计算一个集合中具有某种性质的元素个数比起直接计算来得简单 例如 计算1到700之间不能被7整除的整数个数 先计算1到700之间能被7整除的整数个数 700 7 100 所以1到700之间不能被7整除的整数个数 700 100 600 5 上面举的间接计数的例子是利用了如下原理 如果A是集合S的子集 则A中的元素个数等于S中的元素个数减去不在A中的元素个数 这个原理可写成 6 原理的重要推广 称之为容斥原理 并且将它运用到若干问题上去 其中包括 错位排列 有限制的排列 禁位排列和棋阵多项式等 7 DeMorgan定理 设A B为全集U的任意两个子集 则 DeMorgan定理的推广 设A1 A2 An为U的子集 则 二 容斥原理 8 证明从略 aUb aUb a b a u a b aUbb u b a aUbb aUb a aUb u aUb aUb 9 1 两个集合的容斥原理设A和B是分别具有性质P1和P2的元素的集合 则 例6 1求1到500之间能被5或7整除的正整数个数 解设A为被5整除的整数集合 B为被7整除的整数集合 用 x 表示x的整数部分 则有 10 同时被5和7整除的整数个数 故能被5或7整除的整数个数 11 2 三个集合上的容斥原理设A B C为任意三个集合 则有 3 n个集合上的容斥原理 设A1 A2 An是有限集合 则有 12 4 集合n中不具有a1 a2 a3 之一元素的个数为 余集形式 13 例求在1到10000的整数中不能被4 5 6任意一个整除的数的个数 解 令Ai i 4 5 6 表示1到10000的整数中能被i整除的数的个数 则 14 三 容斥原理的应用实例1 错排问题利用容斥原理很容易理解错排数列通项公式的组合意义 15 1 n 的错位排列个数记为Dn 结论如下 可以用容斥原理证明 设S 1 2 3 n 的集合 S0为S的全排列 则s0 n 令Aj表示排列1 2 n中使j位置上的元素恰好是j的排列的集合 j 1 2 n 则排列12 n的所有错位排列组成集合 16 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 个 应用容斥原理得到 17 18 课堂思考题 被毁坏的玉米地 问题描述 哈姆 外星人又在那了 埃塞和哈姆他们的玉米地是长方形的 每年在丰收之前 他们的玉米地都会很奇怪地遭到毁坏 据埃塞说是外星人干的 所有破坏的地方都是以1米为半径的圆 哈姆发现 如果在玉米地上建立一个适当的直角坐标系的话 那些圆心的坐标将都为整数 万幸的是 埃塞和哈姆有玉米保险 但必须把损坏的面积统计出来 输入文件 CROP IN 输入文件的第一行为一个整数N O N 200 表示圆圈的个数 以下N行每行有两个整数x和y 由空格分开 代表圆心坐标 数据中不存在两个完全重合的圆 输出文件 CROP OUT 输出统计出的总面