容斥原理和鸽巢原理

《容斥原理和鸽巢原理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、容斥原理和鸽巢原理§1容斥原理例求[1，20]中2或3的倍数的个数。[解]2的倍数是：2,4,6,8,10,12,14,16,18,20.←(10个)3的倍数是：3，6，9，12，15，18。←(6个)但答案不是10+6=16个，因为6，12，18在两类中重复计数，应减去。故答案是：16-3=13容斥原理和鸽巢原理容斥原理研究有限集合的交或并的计数。[DeMorgan定理]:设论域U，补集A的补集定义为,则有(a)(b)容斥原理和鸽巢原理DeMogan定理的推广：设：容斥原理和鸽巢原理容斥原理：最简单的计数

2、问题是求有限集合A和B的并的元素数目。显然有定理：UBA容斥原理和鸽巢原理定理：ABCU容斥原理和鸽巢原理例：一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？解：令，M为修数学的学生集合；P为修物理的学生集合；C为修化学的学生集合；所以有容斥原理和鸽巢原理即学校学生数为336人。容斥原理和鸽巢原理一般地，我们可得定理：定理：设A1,A2,…

3、,Am均为有限集，m≥2,则容斥原理和鸽巢原理，其中N是集合U的元素个数，即不属于A的元素个数等于集合的全体减去属于A的元素的个数。一般有：容斥原理指的就是这两个式子。容斥原理和鸽巢原理例1求a,b,c,d,e,f六个字母的全排列中不允许出现ace和df图象的排列数。解：设A为ace作为一个元素出现的排列集，B为df作为一个元素出现的排列集，则A∩B为同时出现ace、df的排列数。根据容斥原理，不出现ace和df的排列数为：=6!-(5!+4!)+3!=582容斥原理和鸽巢原理例2求从1到500的整数中能被

4、3或5除尽的数的个数。解：令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合,则容斥原理和鸽巢原理例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位符号串集合即为容斥原理和鸽巢原理§2错排问题n个元素依次给以标号1，2，…，n。n个元素的全排列中

5、，求每个元素都不在自己原来位置上的排列数。设Ai为数i在第i位上的全体排列，i=1，2，…，n。因数字i不能动，因而有：容斥原理和鸽巢原理所以每个元素都不在原来位置的排列数为容斥原理和鸽巢原理例1数1，2，…，9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。解：实际上是1，3，5，7，9五个数的错排问题，总数为：容斥原理和鸽巢原理例2.在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来上的错排数目。解：8个字母的全排列中，令A1,A2,A3,A4分别表A,

6、C,E,G在原来位置上的排列，则错排数为：容斥原理和鸽巢原理§3棋盘多项式和有限制排列例4个x，3个y，2个z的全排列中，求不出现xxxx，yyy，zz的排列。解设出现xxxx的排列的集合记为A1，

7、A1

8、=6!/(1!×3!×2!)=60;设出现yyy的排列的集合记为A2，

9、A2

10、=7!/(4!×1!×2!)=105；设出现zz的排列的集合记为A3，

11、A3

12、=8!/(4!×3!×1!)=280；1.有限制排列容斥原理和鸽巢原理同时有：

13、A1∩A2

14、=4!/(1!×2!×1!)=12；

15、A1∩A3

16、=5!/

17、(1!×3!×1!)=20；

18、A2∩A3

19、=6!/(4!×1!×1!)=30；

20、A1∩A2∩A3

21、=3!=6；全排列的个数为:9!/(4!×3!×2!)=1260；所以：

22、A1∩A2∩A3

23、=1260－(60+105+280)+(12+20+30)－6=871容斥原理和鸽巢原理2．棋子多项式n个不同元素的一个全排列可看做n个相同的棋子在n×n的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子xxxxx如图所示的布局对应于排列41352。容斥原理和鸽巢原理可以把棋盘的形状推广到任意形状：布子规定称为无

24、对攻规则，棋子相当于象棋中的车。令rk（C）表示k个棋子布到棋盘C上的方案数。如：容斥原理和鸽巢原理r1()=1，r1()=2，r1()=2，r2()=0，r2()=1。为了形象化起见，（）中的图象便是棋盘的形状。容斥原理和鸽巢原理定义设C为一棋盘，称R(C)=∑rk(C)xk为C的棋盘多项式。k=0∞规定r0(C)=1，包括C=f时。设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子