棋盘多项式的计算

棋盘多项式的计算【基金项目】2016年4月25日广西高校中青年教师基础能力提升项目――组合批处理码及其应用(KY2016LX557)；2014年5月19日广西师范大学漓江学院科研项目――组合批处理码的最优值问题研究(201416C).棋盘多项式是组合数学中用于解决有限制条件排列问题的一种方法，它在禁位排列、博弈问题等方面有广泛的应用[1-5].使用棋盘多项式的方法解决有限制条件排列问题，相比递推关系或容斥原理的方法，可操作性强，步骤简单，易于掌握，但计算较为复杂.在文[1]中，牛立新介绍了四种计算方法：直接观察法、分部相乘法、关键点递归法和组合法，其中直接观察法用于简单的棋盘，组合法多用于计算机编程，分部相乘法和关键点递归法则为较常用方法.本文将重点介绍关键点递归法，并利用该方法计算一些特殊棋盘的棋盘多项式.一、基本概念及性质图1对于n个元素的一个排列，可以看作是n个棋子在nxn棋盘上的一种布局：当一个棋子置于棋盘的某一个格子时，则这个棋子所在的行和列都不允许布上任何棋子，即棋盘的每行每列有且只有一个棋子[6].例如，图1对应一个排列34125.5X5的棋盘是一种规则的棋盘，我们可将棋盘推广到任意情况，但还是要求每行每列有且只有一个棋子.例如，棋盘，1个棋子有两种布局方案：和，但不存在两个及两个以上棋子的布局方案.若对棋盘C,令rk(C)表示用k个棋子布到C上的不同方案数，则r1()=1，r1()=r1()=2，r2()=r2()=0.因此，我们引入棋盘多项式的概念.假设棋盘C最多可布n个棋子，则称R(C)=Enk=0rk(C)xk为棋盘C的棋盘多项式.并规定r0(C)=1,即0个棋子布在棋盘C上的不同方案数为1；R()=1,其中表示一个空棋盘，也记作R()=1.对于棋盘C的任一格子无非有两种可能： 要么布棋子，要么不布棋子.我们可令C(i)表示棋盘C中某一格子所在的行和列被删除之后的剩余部分，C(e)表示从棋盘C中去掉该格子后的棋盘,从而得到关于棋盘多项式的两个重要性质.性质1rk(C)=rk-1(C(i))+rk(C(e)).性质2R(C)=xR(C(i))+R(C(e)).此外，若棋盘C是由相互隔离的两个棋盘C1和C2组成，即两个棋盘C1和C2不存在格子同行或同列，那么rk(C)和R(C)还有一个很好的性质.性质3若棋盘C是由相互隔离的两个棋盘C1和C2组成，rk (C) =E ki=0ri (C1) rk-i (C2), R(C) =R(C1) R(C2).二、关键点递归法在求棋盘多项式时，我们经常会使用直接观察法、分部相乘法和关键点递归法，而关键点递归法则融合了前面两种方法.首先，它在棋盘中选择关键点，依据性质 2,把棋盘C分解成两个相互隔离的棋盘C1和C2,方便使用性质3,其实质就是分部相乘法；对于两个新的棋盘C1和C2,重新选择关键点，把它们分解成简单棋盘,便可使用直接观察法；若分解的棋盘还较为复杂,可重复操作,直至算出结果.然而,其过程重复的次数与关键点的选择有着密切的关系.一般地,好的关键点有如下特点,可根据这些特点来选择：(1)关键点所在行和列可布棋子的格子数最多；(2)关键点一般位于棋盘的拐角处；(3)除去关键点的格子后,剩下的棋盘为可分离的棋盘或简单的几部分 .如在图2中,A和B满足上述三个条件,它们都是关键点,可应用关键点递归法计算其棋盘多项式.R(C)=xR()+R()=xR()+[xR()+R()]=2xR()+R3()=2x(x+1)+(x+1)3=1+5x+5x2+x3.三、特殊棋盘的棋盘多项式根据关键点递归法，我们可计算一些特殊棋盘的棋盘多项式，方便人们在计算棋盘多项式时使用.棋盘1R(C)=(1+x)n=Enk=0C(n,k)xk(n为正整数).证明因为R()=1+x,故由性质3可得R(C)=(1+x)n.棋盘2R(C)=Emk=0C(m,k)p(n,k)xk(m,n为正整数且m<n).证明棋盘2是一个nXm的规则棋盘，可先从m列中选取其中的k列布放棋子，有C(m，k)种方法，然后，第1个棋子有n种布局方法,第2个棋子有n-1种,直到第k个棋子有n-k+1种.从而rk(C)=C(m,k)n?(n-1)•••(n-k+1)=C(m,k)P(n,k)，故由棋盘多项式的概念可得 R(C)=Emk=0C(m,k)p(n,k)xk.棋盘3R(C)=1+(a+b+c)x+(ab+ac+bc-a-c)x2+ac(b-2)x3(a,b,c为正整数且b>2).?C明应用关键点递归法，前后选择第 1行第a+1列和第b行第a+1列的格子应用性质2,便得到棋盘3的棋盘多项式.R(C)=xR()+R()=xR()+[xR()+R()]=xR()+[xR()+R()R()R()]=x(1+cx)+x(1+ax)+(1+ax)[1+(b-2)x](1+cx)=1+（a+b+c）x+（ab+ac+bc-a-c）x2+ac（b-2）x3.四、结束语本文