棋盤多項式的計算

李勇剛　秦麗珍

【摘要】 本文介紹了棋盤多項式的基本概念及其性質，并討論關鍵點遞歸法中關鍵點的確定方法，以方便人們尋找關鍵點進行簡便運算，最后，給出了幾個特殊棋盤的棋盤多項式.

【關鍵詞】 禁位排列；棋陣多項式；關鍵點遞歸法

【基金項目】 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.