论文部分内容阅读
【摘要】 本文介绍了棋盘多项式的基本概念及其性质，并讨论关键点递归法中关键点的确定方法，以方便人们寻找关键点进行简便运算，最后，给出了几个特殊棋盘的棋盘多项式.
【关键词】 禁位排列；棋阵多项式；关键点递归法
【基金项目】 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.
【关键词】 禁位排列；棋阵多项式；关键点递归法
【基金项目】 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.