| 标题 | 棋盘多项式的计算 |
| 范文 | 李勇刚 秦丽珍 【摘要】 本文介绍了棋盘多项式的基本概念及其性质，并讨论关键点递归法中关键点的确定方法，以方便人们寻找关键点进行简便运算，最后，给出了几个特殊棋盘的棋盘多项式. 【关键词】 禁位排列；棋阵多项式；关键点递归法 【基金项目】 2016年4月25日广西高校中青年教师基础能力提升项目——组合批处理码及其应用（KY2016LX557）； 2014年5月19日广西师范大学漓江学院科研项目——组合批处理码的最优值问题研究（201416C）. 棋盘多项式是组合数学中用于解决有限制条件排列问题的一种方法，它在禁位排列、博弈问题等方面有广泛的应用[1-5].使用棋盘多项式的方法解决有限制条件排列问题，相比递推关系或容斥原理的方法，可操作性强，步骤简单，易于掌握，但计算较为复杂.在文[1]中，牛立新介绍了四种计算方法：直接观察法、分部相乘法、关键点递归法和组合法，其中直接观察法用于简单的棋盘，组合法多用于计算机编程，分部相乘法和关键点递归法则为较常用方法.本文将重点介绍关键点递归法，并利用该方法计算一些特殊棋盘的棋盘多项式. 一、基本概念及性质 图1 对于n个元素的一个排列，可以看作是n个棋子在n×n棋盘上的一种布局：当一个棋子置于棋盘的某一个格子时，则这个棋子所在的行和列都不允许布上任何棋子，即棋盘的每行每列有且只有一个棋子[6].例如，图1对应一个排列34125. 5×5的棋盘是一种规则的棋盘，我们可将棋盘推广到任意情况，但还是要求每行每列有且只有一个棋子.例如，棋盘 ，1个棋子有两种布局方案： 和 ，但不存在两个及两个以上棋子的布局方案.若对棋盘C，令rk（C）表示用k个棋子布到C上的不同方案数，则 r1（ ）=1，r1（ ）=r1（ ）=2，r2（ ）=r2（ ）=0. 因此，我们引入棋盘多项式的概念. 假设棋盘C最多可布n个棋子，则称 R（C）=∑ n k=0 rk（C）xk 为棋盘C的棋盘多项式.并规定r0（C）=1，即0个棋子布在棋盘C上的不同方案数为1；R（）=1，其中表示一个空棋盘，也记作R（ ）=1. 对于棋盘C的任一格子无非有两种可能：要么布棋子，要么不布棋子.我们可令C（i）表示棋盘C中某一格子所在的行和列被删除之后的剩余部分，C（e）表示从棋盘C中去掉该格子后的棋盘，从而得到关于棋盘多项式的两个重要性质. 性质1 rk（C）=rk-1（C（i））+rk（C（e））. 性质2 R（C）=xR（C（i））+R（C（e））. 此外，若棋盘C是由相互隔离的两个棋盘C1和C2组成，即两个棋盘C1和C2不存在格子同行或同列，那么rk（C）和R（C）还有一个很好的性质. 性质3 若棋盘C是由相互隔离的两个棋盘C1和C2组成，则 rk（C）=∑ k i=0 ri（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. 三、特殊棋盘的棋盘多项式 根据关键点递归法，我们可计算一些特殊棋盘的棋盘多项式，方便人们在计算棋盘多项式时使用. 棋盘1 R（C）=（1+x）n=∑ n k=0 C（n，k）xk（n为正整数）. 证明 因为R（ ）=1+x，故由性质3可得R（C）=（1+x）n. 棋盘2 R（C）=∑ m k=0 C（m，k）p（n，k）xk（m，n为正整数且m≤n）. 证明 棋盘2是一个n×m的规则棋盘，可先从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）=∑ m k=0 C（m，k）p（n，k）xk. 棋盘3 R（C）=1+（a+b+c）x+（ab+ac+bc-a-c）x2+ac（b-2）x3（a，b，c为正整数且b≥2）. 證明 应用关键点递归法，前后选择第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. 四、结束语 本文对棋盘多项式的关键点递归法进行分析，并得到三种特殊棋盘的棋盘多项式，方便人们计算时使用.然而，在实际的应用过程中，人们还会遇到很多特殊的棋盘和具有特殊规律的棋盘多项式.若能加以总结归纳，势必方便人们使用棋盘多项式解决实际问题. 【参考文献】 [1]牛立新，王功明，李洪淇，刘旭敏.棋盘多项式生成算法及其在禁位排列中的应用[J].计算机工程与应用，2006（10）：91-93. [2]顾永跟.棋盘多项式在图论中的应用及其求解算法[J].湖州师专学报，1999，21（5）：44-50. [3]赵泽茂，许彪.禁位排列问题[J].河海大学常州分校学报，2000，41（2）：31-35. [4]宋传宁，邱懿.棋盘多项式的应用[J].上海师范大学学报（自然科学版），1999，28（4）：31-34. [5]李有梅，李素珍.棋盘多项式与夫妻分座问题[J].山西大学学报（自然科学版），1997，20（4）：389-395. [6]卢开澄，卢华明.组合数学（第4版）[M].北京：清华大学出版社，2006. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。