软件2010组合数学第四章容斥原理(二).ppt

1、,第四章 容斥原理 Inclusion and Exclusion Principle (包含排斥原理),主要内容 4.1 容斥原理 4.2 多重集的r-组合数 4.3 错位排列 4.4 有限制条件的排列问题 4.5 有禁区的排列问题 4.6 Mbius反演,应用,这时容斥原理可叙述为： 定理4.1.1 （容斥原理） S中不具有性质P1, P2,Pm的元素数是,对称筛公式,这样定理4.1.1就变成下面的形式：,3, 引入如下的记号： 则定理4.1.1的公式可写成：,定理4.1.2（Jordan公式） 集合 S中恰具有r(0r m)种性质的事物的个数 （广义包含排斥原理）,例4.2.1 确定多重

2、集S=3a,4b,5c的10-组合数。, 4.2 多重集的r-组合数,求多重集S=n1a1, n2a2, ,nkak r-组合数 假定每个nir，i=1,2,n. 用容斥原理求S的r-组合数， 第五章将介绍另外一种方法-生成函数的方法,解：令T= a, b， c ,T的所有10-组合构成集合W,根据定理3.3.3得： 任取T的一个10-组合， 如果其中的a多于3个，则称它具有性质P1; 如果其中的b多于4个，则称它具有性质P2; 如果其中的c多于5个，则称它具有性质P3， 因此S的10-组合数就是W中同时不具有性质P1,P2和P3的元素个数，即W中同时满足a的个数小于等于3，b的个数小于等于4

3、， 并且c的个数小于等于5的10-组合个数。,令Ai= x|xW并且x具有性质Pi A1中的每个10-组合至少含有4个a, 把4个a 拿走就得到T的一个6-组合。反之，对T的 任意一个6-组合加上4个a就得到A1的一个 10-组合，所以|A1|就是T的6-组合数，即 同理可得：,用类似的方法可以计算 所以S的10-组合数为,列出这6个10-组合如下： 1a,4b,5c， 2a,3b,5c， 2a,4b,4c 3a,2b,5c， 3a,3b,4c， 3a,4b,3c,多重集的r组合数等于方程的非负整数解的个数。 用容斥原理来确定方程的非负整数解的个数,例4.2.2 确定方程 x1+x2+x3=1

4、2 (-1 x1 2, 1 x2 5, 2 x3 7) 的整数解的个数.,解：令y1= x1+1, y2= x2-1, y3= x3-2, 则有0 y1 3， 0 y2 4， 0 y3 5， 用y1-1代替 x1 ，y2+1代替x2，y3+2代替x3得：y1+y2+y3=10 (0 y1 3， 0 y2 4， 0 y3 5) 这个方程的整数解的个数就是原来方程的整数解的个数，即为多重集3a,4b,5c的10-组合数。参照例4.2.1的方法，结果为6。, 4.3 错位排列,错位排列源自一个古老的“装错信封问题”，它是由数学家约翰伯努利(Johann Bernoulli)的儿子丹尼尔伯努利(Dan

5、id Bernoull)提出来的，并曾被著名数学家欧拉(Euler)称为“组合数论的一个妙题”。其大意为：一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？ 这个问题就是一个典型的错位排列问题。,设=1,2,n, 的一个错位排列就是排列 i1i2in, 且ijj, j=1,2, ,n. 用Dn表示的错位排列数。,一、定义,二、计算公式 当n=1时，不存在错位排列， D1=0; 当n=2时，错位排列只有21， D2=1;,对于一般的n, 有以下的定理. 定理4.3.1 对于n1有,当n=3时，错位排列有231, 312， D3=2; 当n=4时，

6、错位排列有 2143,2341,2413,3142,3412,3421,4123,4312,4321， D4=9; ,证明： 设 = 12,n， X=1,2,n. S-X的所有排列的集合。 性质Pj-在一个排列中，如果j在第j个位置上，则该排列具有性质Pj,对j=1,2,n,. Aj表示S中具有性质Pj的排列的集合， 则 的错位排列数就是 中的排列。,（1）A1中的排列具有下面的形式1i1i2in, 其中i1i2in是2,3,n的一个排列， 所以 。 同理，对于j= 2,3,n,有 (2) 中的排列具有下面的形式：12i3in ，其中i3i4in是3,4,n的一个排列，所以 同理，对于1,2,

7、n的任何一个2-组合i,j有：,(3) 一般的，对于任意的整数k, 1kn, 有 其中i1,i2,ik是1,2,n的一个k-组合。 根据容斥原理得：,三、Dn的递推关系1,三、Dn的递推关系2 Dn=(n-1)(Dn-1+Dn-2), n3, n为整数 D1=0, D2=1 根据这个等式可以计算任意一个Dn的值。,所以 当n比较大的时， 而 表示 的 错位排列数与X的排列数之比，即错位排列数 出现的概率，这说明在n很大的时候，这个概 率可看作1/e。,四、例题（例4.3.1） （1）重新排列123456789，使得偶数在原来的位置上而奇数不在原来的位置上，问有多少种排法？ （2）如果要求只有4

8、个数在原来的位置上，问有多少种排法？,解：（1）这是1，3，5，7，9五个数的错排问题，根据定理4.3.1得：,（2）先从123456789中选取4个数的取法为C(9,4), 再对其他5个数的错位排列，错位排列数为D5，根据乘法法则有：,例P71(4.8) 证明下列等式 证明：将S=1,2,n的所有排列分成下列 情况，没有一个数在其自然位置上的排列 数为 ；恰有i个数在其自然位 置上的排列数为 (i=1,2,n), 根据加 法法则，而所有的排列个数为n!,等式成立。,错位排列的限制是对元素排列位置的限制。 本节介绍另外一类有限制条件的排列问题， 是对元素之间的相邻关系的限制。, 4.4 有限制

9、条件的排列问题,例: 有八个孩子外出散步，他们排成 成一列，记作a1 a2 a8,其中a1排在最前面， a8排在最后面。现在对这八个孩子重新排列成 ai1 ai2 ai8,使得没有ai和ai+1在队列中出现， 1i7, 问有多少种排列的方式？ 这个问题就是一个有限制条件的排列问题.,一、定义 一般来说，令I=1,2,n，在I的排列中不出现12,23,34,(n-1)n的排列就叫做有限制条件的排列，把这种排列的个数记为Qn.,二、当n=1时，Q1=1;,当n=2时，所求排列为21， Q2=1;,当n=3时，所求排列为213,321, 132, Q3=3;,对于一般的正整数n，有下面的定理： 定理

10、4.4.1 对于n1有,当n=4时，所求排列为4132,4321,4213,3214, 3241,3142,2431,2413,2143,1324,1432，所以 Q4=11;,证明：设I=1,2,n，I的排列有n!个， S-这些排列构成的集合. 性质Pj -如果X的排列中有j(j+1)出现，则称这个排列具有性质Pj,对于j= 1,2,n-1, Aj -具有性质Pj的排列构成的子集， 则 (1) 先计算|A1|,一个排列属于A1当且仅当12出现在这个排列里. 所以A1中的排列就是12,3,4,n的一个排列, 因此|A1|=(n-1)!,同理对j=2,n-1,也有|Aj|=(n-1)!,(2)然

11、后计算|AiAj|，其中i,j是1,2,n-1的一个2-组合，一个排列属于AiAj 当且仅当i(i+1)和j(j+1)都出现在这个排列里. 分两种情况： (2.1) i+1=j, 这时排列中出现i(i+1)(i+2),这种排列就是 1,2,i-1,i(i+1)(i+2),i+3,n-1的一个排列, 因此|AiAj|=(n-2)! (2.2) i+1j, 这时排列中出现i(i+1)和j(j+1),这种排列就是 1,2,i-1,i(i+1),j(j+1),n-1的一个排列, 因此|AiAj|=(n-2)! (3)同理，对于任意的1kn-1,有,根据包含排斥原理得证。,三、有限制条件的排列与错位排列

12、的联系 将定理4.4.1的等式变形得到： Qn=Dn+Dn-1 证明：,四、有限制条件的环排列问题 有n个小孩坐在旋转木马上，如果让他们交换座位，使得每个小孩前面都不是他原来前面的孩子，问有多少种方法？,解：设 I=1,2,n，I的排列有(n-1)!个， S-这些排列构成的集合. 性质Pj -如果X的环排列中有j(j+1)出现j= 1, ,n-1, 则称这个环排列具有性质Pj,对于,Aj -具有性质Pj的环排列构成的子集， 则利用与定理5.3类似的方法不难得到,棋盘多项式 有禁区的排列问题求解 例题, 4.5 有禁区的排列问题,有禁区的排列问题,指一类对元素排列位置有限制的问题。 例如：不允许

13、1排在第2位； 且不允许2排在第3位；,1 2 3 4,1 2 3 4,棋盘布棋问题,1 2 3 4,1 2 3 4,棋盘的行表示X中元素 列表示相应元素在排列中的位置,设 I=1,2,n 则I的一个排列恰好对应n个相同棋子在nn的棋盘上的一种布棋方案。,这种布棋方案对应排列3124,如果在排列中限制元素i不能排在第j个位置，则相应的布棋方案中棋盘的第i行和第j列的方格不允许放棋子。将所有不允许放棋子的方格称为禁区。,设C是一个棋盘， 表示把k个相同的棋子布到C中的方案数。 在布棋时我们规定：当一个棋子放到C中的某个格以后，这个格所在的行和列就不能再放其他的棋子了。 规定对任意的棋盘C有： (

14、C)=1,一、布棋方案数,),(,2,= 1,r,布棋方案数 （C）具有如下性质,（1）对于任意的棋盘C和正整数k，如果k大于C中的方格数，则 （C）=0。 （2）（C）等于C中的方格数。 （3）设C1和C2是两个棋盘，如果C1经过旋转或者翻转就变成了C2，则 (C1)= (C2)。 （4）设Ci是从棋盘C中去掉指定的方格所在的行和列以后剩余的棋盘，Cl是从棋盘C中去掉指定的方格以后剩余的棋盘，则有,(5) 设棋盘C由两个子棋盘C1和C2组成，如果C1和C2的布棋方案是互相独立的，则有,图(a) C1和C2的布棋方案相互独立,图(b) C1和C2的布棋方案不相互独立,二、棋盘多项式 定义4.5

15、.1 设C是棋盘，则,叫做棋盘多项式.,R(C)一般只有有限项。,R(C)的性质,(1) R(C)=xR(Ci)+R(Cl), Ci和Cl含义如前所述。,证明：,(2) R(C)=R(C1)R(C2), , C1和C2含义如前所述。,将以上各式的两边分别相加得：,证明：,解 R ( ) =x R( )+ R( ) =x(1+2x)+ R( ) R( ) =x+2x2 +(1+x)(x R( )+ R( ) ) =x+2x2 +(1+x)(x (1+x)+(1+3x+ x2) =x+2x2 +(1+x)(1+4x+ 2x2) =x+2x2 + (1+5x+ 6x2+2x3) =1+6x+8x2+

16、2x3,例 4.5.1 计算棋盘多项式R( ),例 计算R( ),解：R( )=xR( )+R( ) =xR( )+R( )R( ) =x(1+2x+x2)+(1+2x)(1+3x+x2) = 1 + 6x + 8x2 + 3x3,R( )=xR( )+R( ) =x(1+x)+(1+2x)=1+3x+x2,R( )=xR( )+R( ),=xxR( )+R( ) +xR( )+R( ) =xx(1+2x)+(1+3x+x2)+ x(1+3x+x2)+1+4x+3x2 =1+6x+10 x2+4x3,定理4.5.1 设C是nn的具有给定禁区的棋盘，这个禁区对应于集合1,2,n中的元素在排列中不

17、允许出现的位置。则这种有禁区的排列数是 n!-r1(n-1)!+ r2(n-2)!-+(-1)nrn 其中ri表示i个棋子布置到禁区的方案数。,三、有禁区的排列问题,利用棋盘多项式,证明： (1)S-带编号的棋子布到nn棋盘上的方案构成的集合。n个棋子布到nn棋盘上方案有n!个。 如果对n个棋子分别编号1,2,n，并且认为编号不同的棋子放入同样的方格是不同的放置方案，那么这些方案数是n！ n！ Pj-第j个棋子落入禁区的性质，j= 1,2,n Aj-S中具有性质Pj的方案构成的子集， 那么所求的排列数就是,(2) 1号棋子落入禁区的方案数为r1，当它落入禁区的某一格以后，2,3,n号棋子可以任

18、意放置在(n-1)(n-1)的棋盘上，由乘法法则得: |A1|=r1(n-1)!(n-1)! 同理对i= 2,3,n有 |Ai|=r1(n-1)!(n-1)! 对i求和得： (3) 1号和2号两个棋子落入禁区的方案数为2r2, 它们落入以后， 3,4,n号棋子可以任意 放置在(n-2)(n-2)的棋盘上，所以,|A1 A2|=2r2(n-2)!(n-2)!,同理对i,j1,2,n有|Ai Aj|=2r2(n-2)!(n-2)!， 对所有的1 ij n求和有, |A1 A2 An |=rnn! (4) 根据包含排斥原理，带编号的n个棋子都不落入禁区的方案数是 (5) 而带编号的方案数与不带编号的方案数相差n!倍，因此结论成立，即：,这个定理适用于小禁区的布棋问题， 如果是mn的禁区或者是很大的禁区， 那么只能