《chap容斥原理、棋盘多项式和有限制条件排列.ppt》由会员分享，可在线阅读，更多相关《chap容斥原理、棋盘多项式和有限制条件排列.ppt（37页珍藏版）》请在三一文库上搜索。
1、计数问题是组合数学研究的重要问题之一。已学过的一些计数方法：如 加法法则，母函数方法等；两个重要的计数原理：和Plya。本次课我们先学习容斥原理及其应用。,3.1 容斥原理,解： 2的倍数是：2，4，6，8，10，12，14，16，18，20。共10个；,3.1 容斥原理,例1 求不超过20的正整数中2或3的倍数的个数。,否！因为6，12，18在两类中重复计数，应减去。,3 的倍数是：3，6，9，12，15，18。共 6个；,答案是10+6=16个吗？,故答案是：16-3=13,对于求两个有限集合A和B的并的元素数目，我们有,即具有性质A或B的元素的个数等于具有性质A的元素个数和具有性质B的元
2、素个数减去同时具有性质A和B的元素个数。,3.1 容斥原理,3.1 容斥原理,A,B,AB,U,3.1 容斥原理,定理2,3.1 容斥原理,A,B,C,AB,AB C,BC,AC,U,例2 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。假设每个学生至少修一门课，问这学校共有多少学生？,3.1 容斥原理,解：令A为修数学的学生集合； B 为修物理的学生集合； C 为修化学的学生集合；,即学校学生数为336人。,3.1 容斥原理,同理可推出：,利用数学归纳
3、法可得一般的定理：,3.1 容斥原理,3.1 容斥原理,3.1 容斥原理,(5),容斥原理指的就是（4）和（5）式。用来计算有限集合的并或交的元素个数。,例3 求从1到500的整数中能被3或5除尽的数的个数.,3.1 容斥原理,解：令A为从1到500的整数中被3除尽的数的集 合，B为被5除尽的数的集合,被3或5除尽的数的个数为,解：令A、B、C分别为不出现a，b，c符号的集合。,即有,3.1 容斥原理,例4 求由a,b,c,d四个字母构成的n位符号串中a,b,c都至少出现一次的符号串数目。,a,b,c都至少出现一次的n位符号串数目为,3.1 容斥原理,例5 用26个英文字母作不允许重复的全排列
4、，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。,3.1 容斥原理,解：所有排列中，令,则,出现dog字样的排列，相当于把dog作为一个单元参加排列，故,类似有：,由于god,dog不可能在一个排列中同时出现，故：,3.1 容斥原理,由于gum,dog可以在dogum中同时出现，故有：,类似有,3.1 容斥原理,3.1 容斥原理,其余多于3个集合的交集都为空集。,3.1 容斥原理,故满足要求的排列数为：,1. 再解错排问题,n个元素依次给以标号1，2，n。n个元素 的全排列中，求每个元素都不在自己原来位置 上的排列数。 设Ai 为元素i在第i位上的全
5、体排列, i=1,2,n。 则有|U|=n!， 因元素i不能动，因而有：,3.2 容斥原理应用,同理,每个元素都不在原来位置的排列数为,3.2 容斥原理应用,3.2. 容斥原理应用,2.1 棋盘多项式,n个不同元素的一个全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子,x,x,x,x,x,排列41352对应于如图所示的布局。,3.2. 容斥原理应用,可以把棋盘的形状推广到任意形状：,布子规定同上。,令rk (C)表示k个棋子布到棋盘C上的方案数。,3.2. 容斥原理应用,3.2. 容斥原理应用,规定 r0(C)=1，包括C=时。设Ci是棋盘C的某一指定
6、格子所在的行与列都去掉后所得的棋盘；Ce是仅去掉该格子后的棋盘。在上面定义下，显然有,rk(C)=rk-1(Ci)rk(Ce),3.2. 容斥原理应用,从而,3.2. 容斥原理应用,例如：,3.2. 容斥原理应用,如果C由相互分离的C1，C2组成，即C1的任一格子所在的行和列中都没有C2的格子。则有：, R(C) = R(C1) R(C2) (4),故,3.2. 容斥原理应用,利用()和()，可以把较复杂的棋盘逐步分解成相对比较简单的棋盘，从而得到其棋盘多项式。,3.2. 容斥原理应用,2.2 有禁区的排列,例设对于排列P=P1 P2 P3 P4，规定P1， P,4， P2,， P42。,这样
7、的排列对应于有禁区的布子。如左图有影线的格子表示禁区。,3.2. 容斥原理应用,定理:设 rk 为 k 个棋子布入禁区的方案数，k = 1, 2,n。则有禁区的布子方案数（即禁区内不布子的方案数）为,3.2. 容斥原理应用,例2 ,四位工人，A,B,C,D四项任 务。 条件如下： 不干B； 不干B、C； 不干C、D；不干D。 问有多少种可行方案？,3.2. 容斥原理应用,解:由题意，可得如下棋盘：,其中有影线的格子表示禁区。,方案数=4!6(41)!+10(42)!4(43)! +0(44)!=4,3.2. 容斥原理应用,例3三论错排问题 错排问题对应的是nn的棋盘的主对角线 上的格子是禁区的布子问题。,R(C)=,则有,故错排问题的解为 :,欧拉函数是指小于n且与n互素的正整数的个数。,设1到n的n个数中pi 倍数的集合为,解：若n分解为素数的乘积,3.2. 容斥原理应用,3 欧拉函数(n),3.2. 容斥原理应用,则有,3.2. 容斥原理应用,