5 容斥原理与鸽笼原理.pptx

1
第五讲
容斥原理与鸽笼原理
《图论与组合优化》
2
一. 引言
●容斥原理是组合数学中的一个重要
原理,它在计数问题中占有很重要地位.
●容斥原理所研究的问题是与若干有
限集的交、并或差有关的计数.
●在实际工作中, 有时要计算具有某种
性质的元素个数.
例: 某单位举办一个外语培训班, 开设
英语, 法语两门课.
3
●设U为该单位所有人集合, A,B分别为
学英语, 法语人的集合, 如图所示.
●学两门外语的人数为|A∩B|, 只学一门
外语的人数为|A∪B|-|A∩B|, 没参加学****br/>的人数为|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
an定理: 设A, B为全集U的任意
两个子集, 则
an定理的推广: 设A1,A2,,An为
U的子集, 则
二. 容斥原理
8
1. 两个集合的容斥原理
设A和B是分别具有性质P1和P2的元素的集合, 则
求1到500之间能被5或7整除的正整数个数.
解设A为被5整除的整数集合, B为被7整除的整数集合, 用[x]表示x的整数部分, 则有
9
同时被5和7整除的整数个数
故能被5或7整除的整数个数
10
2. 三个集合上的容斥原理
设A, B, C为任意三个集合, 则有
3. n个集合上的容斥原理:
设A1,A2,…,An是有限集合, 则有