组合数学-棋盘多项式和有限制条件的排列

1、3.4 禁区排列概念有禁区的排列概 念对于1,2,3,4的一个排列P=p1p2p3p4，规定p13，p21,4，p32,4，p42。这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。1 2 3 4 p4p1p2p32.3 棋盘多项式和有限制条件的排列2.3 棋盘多项式和有限制排列1棋盘多项式 n个不同元素的一个全排列可看做n个相同的棋子在nn的棋盘上的一个布局。布局满足同一行（列）中有且仅有一个棋子xxxxx 如图所示的布局对应于排列41352。3.4 棋盘排列概念2.3 棋盘多项式和有限制条件的排列概 念棋盘（子）多项式 n个元素的排列可看作n个棋子（車）在nn棋盘C上的一种布局，布

2、子规定称无对攻规则，即同一行（列）有且仅有一个棋子。 棋盘C可推广为任意形状，令rk(C)表示k个棋子布列棋盘C上的方案数，称 为棋盘C的棋盘多项式，规定r0(C)=1，包括C=时。 如r1( )=1，r1( )=2，r1( )=2，r2( )=1 R( )=1+x， R( )=1+2x， R( )=1+2x+x23.4 棋盘排列加法2.3 棋盘多项式和有限制条件的排列概 念棋盘（子）多项式 设C(i)为C的某一指定格子所在行与列去掉后的所得棋盘，C(e)为C是仅去掉该格子后的所得棋盘。如 C： C(i)： C(e)： 显然有rk(C)=rk-1(C(i)+rk(C(e)，R(C)=xR(C(

3、i)+R(C(e)。 如R( )=1+x， R( )=xR( )+R( )=x+(1+x)=1+2x， R( )= xR( )+R( )=x(1+x)+(1+x)=1+2x+x2 *3.4 棋盘排列乘法2.3 棋盘多项式和有限制条件的排列概 念棋盘（子）多项式 设C由相互分离的C1、C2组成，即C1的任一格子所在的行和列中都没有C2的格。有：R(C)=R(C1) R(C2)。如R( )=R( )R( )=(1+x)(1+x)=1+2x+x2 R( )=xR()+R( )=x+(1+2x+x2)=1+3x+x2R( )=xR( )+R( )=x(1+2x)+(1+3x+x2)=1+4x+3x2

4、R( )=xR( )+R( )= xR( )+xR( )+R( ) =x(1+4x+3x2)+x(1+3x+x2)+(1+4x+3x2 )=1+6x+10 x2+4x3*3.4 禁区排列概念有禁区的排列概 念对于1,2,3,4的一个排列P=p1p2p3p4，规定p13，p21,4，p32,4，p42。这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。1 2 3 4 p4p1p2p32.3 棋盘多项式和有限制条件的排列3.4 禁区排列定理8有禁区的排列定理 2.5有禁区的排列数为n!-r1(n-1)! +r2(n-2)!+(-1)nrn 。其中ri是有i个棋子布置到禁区部分的方案数。 证

5、明：设S为n个棋子布入nn棋盘的所有排列的集合，Ai为第i个棋子布入禁区，其他棋子任意布的方案集，i=1,2,3,n。根据题意有|S|=n!。一个棋子落入禁区的方案数为r1，剩下的n-1棋子任意排列，故至少一个棋子落入禁区的方案数为r1(n-1)!。同理，两个棋子落入禁区的方案数为r2，剩下的n-2棋子任意排列，故至少两个棋子落入禁区的方案数为r2(n-2)!，以此类推。 根据容斥原理，无一棋子落入禁区的方案数为2.3 棋盘多项式和有限制条件的排列3.4 禁区排列例1 3.5.2 有禁区的排列例 题例1、有G,L,W,Y四位工作人员，A,B,C,D为四项任务，但G不能从事任务B，L不能从事B,

6、C两项任务，W不能做C,D工作，Y不能从事任务D。若要求每人从事各自力所能及的一项工作，试问有多少种不同方案？ A B C DGLWY解：由题意，可得棋盘如右图，其中有阴影的格子表示禁区。由上述可知R( )=1+6x+10 x2+4x3，即r1=6，r2=10，r3=4，故所求方案数为4!-63!+102!-4=4*2.3 棋盘多项式和有限制条件的排列3.4 禁区排列例2 有禁区的排列例 题例2、设右图是nn棋盘，禁区都在对角线上，用n个棋子在上面布局。求如图所示的有禁区的棋盘的布局方案数。n格n格解：设棋盘中有阴影的格子为禁区C。显然这是一个错排。由上述可知R(C)=R( )n=(1+x)n

7、=1+C(n,1)x+C(n,2)x2+C(n,n)xn，即ri=C(n,i)，故所求方案数为Dn=n!-C(n,1)(n-1)!+C(n,2)(n-2)!+(-1)nC(n,n)注：这是错排公式的另一种推导方式。2.3 棋盘多项式和有限制条件的排列3.5 广义容斥原理概念3.3 广义容斥原理概 念 若将2.1中的例1所问改为“单修一门数学的学生有多少？” “只修一门课的学生有多少？”“只修两门课的学生有多少？”则相应的答案表示如下： 设有与性质r1,r2,rn相关的集合S的子集A1,A2,An，pk表示至少具有k种性质的元素的元次，qk为恰有k种性质的元素个数，有3.5 广义容斥原理定理93

8、.3 广义容斥原理定理 3.9注：q0即通用的容斥原理 。证明：可以利用数学归纳法证明。或用组合分析方法如下：为证明等式成立，只需证明等式右端恰好具有k个性质ri (i=1,2,n)的元素被计算的次数净值为1，而少于或多于k个性质的元素被计算的次数净值为0即可。考虑S中一个恰好具有k个性质的元素x，则其对pk的某一项的贡献为1，而对pk+1,pk+2,pn的贡献都是0。若某一元素具有的性质少于k种，则其对pk,pk+1,pn的贡献都是0。若恰有k+j种性质，则其对pk的贡献是C(k+j,j)，对pk+i的贡献是C(k+j,k+i)，其中 (j=1,2,n-k; i=1,2,j) 。而即恰有k+

9、j种性质，对pk, pk+1, pn的贡献都是0。定理得证。3.5 广义容斥原理例13.3 广义容斥原理例 题例1、某学校有12位教师，已知教数学课的教师有8位，教物理的教师有6位，教化学的教师有5位，其中有5位既教数学又教物理，有4位兼教数学和化学，兼教物理和化学的有3位；有3位教师教三门课，试问教数、理、化以外的课的教师有几位？只教一门课的教师有几位？正好教两门课的教师有几位？解：设全体教师集合为S，令教数学的教师属于A1，教物理的属于A2，教化学的属于A3。则p0=12，p1=|A1|+|A2|+|A3|=8+6+5=19，p2=|A1A2|+|A1A3|+|A2A3|=5+4+3=12

10、，p3=|A1A2A3|=3。故教其他课的老师数为：q0=p0-p1+p2-p3=12-19+12-3=2恰好教一门的教师数为：q1=p1-2p2+3p3=4恰好教两门的老师数为：q2=p2-3p3=33.5 广义容斥原理例23.6 广义容斥原理例 题例2、（n 对夫妻围坐问题二重错排）设 n 对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种可能的方案？解：不妨令n个女人先围成一圈，方案数为(n-1)!。对任一这种给定方案，顺时针给每个女人编号1,2,n。设第i号女人顺时针与下一个女人之间的位置为第i号位置，第i号女人的丈夫的编号也为第i号，1in。让n个男人坐到上述编号的n个位

11、置上。设ai是坐在第i号位置上的男人，则aii,i-1,2in，a1n,1。这样的限制也即要求在下面3行n列的排列中 a1 a2 a3 an-1 an1 2 3 n-1 n n 1 2 n-2 n-1每列中都无相同元素。满足这样的限制的排列a1a2an称为二重错排。设二重错排的个数为Un，原问题所求的方案数就是Un(n-1)!。设Ai为ai=i,i-1,2in，A1为a1=n,1的排列a1a2an的集合，则|Ai|=2(n-1)!，因为Ai表示两个位置集合，关键是计算k个Ai的交集的排列数。考虑(n,1)(1,2)(2,3)(n-1,n)这n对数的k 对中各取一数，且互不相同的取法的计数，这相当于从n,1,1,2,2,3,3,4,n-1,n-1,n中取k个互不相邻数的组合的计数，但首尾的n不能同时取。根据前面的不相邻组合，其计数为C(2n-k+1,k)-C(2n-4-(k-2)+1,k-2)= C(2n-k,k)(2n)/(2n-k)，根据容斥原理，有第3章 小结本章小结 本章主要讨论了容斥原理及其推广定理的概念，及其在排列组合计数中的各种应用，包括：有限元重集的排列、组合、圆排列，错排、多种有禁区排列等。 合理分类是计数的重要方法。在无法简单分类的情况下，要涉及有重复的