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

《软件2010组合数学第四章容斥原理(三).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章容斥原理InclusionandExclusionPrinciple(容斥原理)对称筛公式这样定理4.1.1就变成下面的形式：3,引入如下的记号：则定理4.1.1的公式可写成：定理4.3.1对于n≥1有Dn的递推关系Dn=(n-1)(Dn-1+Dn-2),n≥3,n为整数D1=0,D2=1限制相邻关系条件的线排列，记为Qn.定理4.4.1对于n≥1有限制相邻关系条件的环排列，记为Qn.定理4.4.1对于n≥1有棋盘多项式有禁区的排列问题求解例题§4.5有禁区的排列问题有禁区的排列问题指一类对元素排列位置有限制的问题。例如：不允许

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

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

4、)C1和C2的布棋方案相互独立图(b)C1和C2的布棋方案不相互独立二、棋盘多项式定义4.5.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()=xR()+R()=x(1+2x)+R()R()=x+2x2+(1+x)(xR()+R())=x+2x2+(1+x)(x(1+x)+(1+3x+x2))=x+2x2+(1+x)(1+4x+2x2)

5、)=x+2x2+(1+5x+6x2+2x3)=1+6x+8x2+2x3例4.5.1计算棋盘多项式R()例计算R()解：R()=xR()+R()=xR()+R()R()=x(1+2x+x2)+(1+2x)(1+3x+x2)=1+6x+8x2+3x3R()=x·R()+R()=x(1+x)+(1+2x)=1+3x+x2R()=x·R()+R()=x·[x·R()+R()]+[x·R()+R()]=x[x(1+2x)+(1+3x+x2)]+[x(1+3x+x2)+1+4x+3x2]=1+6x+10x2+4x3定理4.5.1设C是n×n的具有

6、给定禁区的棋盘，这个禁区对应于集合{1,2,…,n}中的元素在排列中不允许出现的位置。则这种有禁区的排列数是n!-r1(n-1)!+r2(n-2)!-…+(-1)nrn其中ri表示i个棋子布置到禁区的方案数。三、有禁区的排列问题利用棋盘多项式证明：(1)S----带编号的棋子布到n×n棋盘上的方案构成的集合。n个棋子布到n×n棋盘上方案有n!个。如果对n个棋子分别编号1,2,…,n，并且认为编号不同的棋子放入同样的方格是不同的放置方案，那么这些方案数是n！×n！Pj-----第j个棋子落入禁区的性质，j=1,2,…,nAj-----S

7、中具有性质Pj的方案构成的子集，那么所求的排列数就是(2)1号棋子落入禁区的方案数为r1，当它落入禁区的某一格以后，2,3,…,n号棋子可以任意放置在(n-1)×(n-1)的棋盘上，由乘法法则得:

8、A1

9、=r1(n-1)!(n-1)!同理对i=2,3,…,n有

10、Ai

11、=r1(n-1)!(n-1)!对i求和得：(3)1号和2号两个棋子落入禁区的方案数为2r2,它们落入以后，3,4,…,n号棋子可以任意放置在(n-2)×(n-2)的棋盘上，所以

12、A1∩A2

13、=2r2(n-2)!(n-2)!同理对{i,j}∊{1,2,…,n}有

14、Ai∩Aj

15、

16、=2r2(n-2)!(n-2)!，对所有的1≤i

17、A1∩A2∩…∩An

18、=rn·n!(4)根据容斥原理，带编号的n个棋子都不落入禁区的方案数是(5)而带编号的方案数与不带编号的方案数相差n!