棋盤多項(xiàng)式的計(jì)算

李勇剛　秦麗珍

【摘要】 本文介紹了棋盤多項(xiàng)式的基本概念及其性質(zhì)，并討論關(guān)鍵點(diǎn)遞歸法中關(guān)鍵點(diǎn)的確定方法，以方便人們尋找關(guān)鍵點(diǎn)進(jìn)行簡(jiǎn)便運(yùn)算，最后，給出了幾個(gè)特殊棋盤的棋盤多項(xiàng)式.

【關(guān)鍵詞】 禁位排列；棋陣多項(xiàng)式；關(guān)鍵點(diǎn)遞歸法

【基金項(xiàng)目】 2016年4月25日廣西高校中青年教師基礎(chǔ)能力提升項(xiàng)目——組合批處理碼及其應(yīng)用（KY2016LX557）； 2014年5月19日廣西師范大學(xué)漓江學(xué)院科研項(xiàng)目——組合批處理碼的最優(yōu)值問(wèn)題研究（201416C）.

棋盤多項(xiàng)式是組合數(shù)學(xué)中用于解決有限制條件排列問(wèn)題的一種方法，它在禁位排列、博弈問(wèn)題等方面有廣泛的應(yīng)用[1-5].使用棋盤多項(xiàng)式的方法解決有限制條件排列問(wèn)題，相比遞推關(guān)系或容斥原理的方法，可操作性強(qiáng)，步驟簡(jiǎn)單，易于掌握，但計(jì)算較為復(fù)雜.在文[1]中，牛立新介紹了四種計(jì)算方法：直接觀察法、分部相乘法、關(guān)鍵點(diǎn)遞歸法和組合法，其中直接觀察法用于簡(jiǎn)單的棋盤，組合法多用于計(jì)算機(jī)編程，分部相乘法和關(guān)鍵點(diǎn)遞歸法則為較常用方法.本文將重點(diǎn)介紹關(guān)鍵點(diǎn)遞歸法，并利用該方法計(jì)算一些特殊棋盤的棋盤多項(xiàng)式.

一、基本概念及性質(zhì)

圖1

對(duì)于n個(gè)元素的一個(gè)排列，可以看作是n個(gè)棋子在n×n棋盤上的一種布局：當(dāng)一個(gè)棋子置于棋盤的某一個(gè)格子時(shí)，則這個(gè)棋子所在的行和列都不允許布上任何棋子，即棋盤的每行每列有且只有一個(gè)棋子[6].例如，圖1對(duì)應(yīng)一個(gè)排列34125.

5×5的棋盤是一種規(guī)則的棋盤，我們可將棋盤推廣到任意情況，但還是要求每行每列有且只有一個(gè)棋子.例如，棋盤 ，1個(gè)棋子有兩種布局方案： 和 ，但不存在兩個(gè)及兩個(gè)以上棋子的布局方案.若對(duì)棋盤C，令rk（C）表示用k個(gè)棋子布到C上的不同方案數(shù)，則

r1（ ）=1，r1（ ）=r1（ ）=2，r2（ ）=r2（ ）=0.

因此，我們引入棋盤多項(xiàng)式的概念.

假設(shè)棋盤C最多可布n個(gè)棋子，則稱

R（C）=∑ n k=0 rk（C）xk

為棋盤C的棋盤多項(xiàng)式.并規(guī)定r0（C）=1，即0個(gè)棋子布在棋盤C上的不同方案數(shù)為1；R（）=1，其中表示一個(gè)空棋盤，也記作R（ ）=1.

對(duì)于棋盤C的任一格子無(wú)非有兩種可能：要么布棋子，要么不布棋子.我們可令C（i）表示棋盤C中某一格子所在的行和列被刪除之后的剩余部分，C（e）表示從棋盤C中去掉該格子后的棋盤，從而得到關(guān)于棋盤多項(xiàng)式的兩個(gè)重要性質(zhì).

性質(zhì)1 rk（C）=rk-1（C（i））+rk（C（e））.

性質(zhì)2 R（C）=xR（C（i））+R（C（e））.

此外，若棋盤C是由相互隔離的兩個(gè)棋盤C1和C2組成，即兩個(gè)棋盤C1和C2不存在格子同行或同列，那么rk（C）和R（C）還有一個(gè)很好的性質(zhì).

性質(zhì)3 若棋盤C是由相互隔離的兩個(gè)棋盤C1和C2組成，則

rk（C）=∑ k i=0 ri（C1）rk-i（C2），R（C）=R（C1）R（C2）.

二、關(guān)鍵點(diǎn)遞歸法

在求棋盤多項(xiàng)式時(shí)，我們經(jīng)常會(huì)使用直接觀察法、分部相乘法和關(guān)鍵點(diǎn)遞歸法，而關(guān)鍵點(diǎn)遞歸法則融合了前面兩種方法.首先，它在棋盤中選擇關(guān)鍵點(diǎn)，依據(jù)性質(zhì)2，把棋盤C分解成兩個(gè)相互隔離的棋盤C1和C2，方便使用性質(zhì)3，其實(shí)質(zhì)就是分部相乘法；對(duì)于兩個(gè)新的棋盤C1和C2，重新選擇關(guān)鍵點(diǎn)，把它們分解成簡(jiǎn)單棋盤，便可使用直接觀察法；若分解的棋盤還較為復(fù)雜，可重復(fù)操作，直至算出結(jié)果.然而，其過(guò)程重復(fù)的次數(shù)與關(guān)鍵點(diǎn)的選擇有著密切的關(guān)系.一般地，好的關(guān)鍵點(diǎn)有如下特點(diǎn)，可根據(jù)這些特點(diǎn)來(lái)選擇：（1）關(guān)鍵點(diǎn)所在行和列可布棋子的格子數(shù)最多；（2）關(guān)鍵點(diǎn)一般位于棋盤的拐角處；（3）除去關(guān)鍵點(diǎn)的格子后，剩下的棋盤為可分離的棋盤或簡(jiǎn)單的幾部分.如在圖2中，A和B滿足上述三個(gè)條件，它們都是關(guān)鍵點(diǎn)，可應(yīng)用關(guān)鍵點(diǎn)遞歸法計(jì)算其棋盤多項(xiàng)式.

R（C）=xR（ ）+R（ ）

=xR（ ）+[xR（ ）+R（ ）]

=2xR（ ）+R3（ ）

=2x（x+1）+（x+1）3

=1+5x+5x2+x3.

三、特殊棋盤的棋盤多項(xiàng)式

根據(jù)關(guān)鍵點(diǎn)遞歸法，我們可計(jì)算一些特殊棋盤的棋盤多項(xiàng)式，方便人們?cè)谟?jì)算棋盤多項(xiàng)式時(shí)使用.

棋盤1 R（C）=（1+x）n=∑ n k=0 C（n，k）xk（n為正整數(shù)）.

證明 因?yàn)镽（ ）=1+x，故由性質(zhì)3可得R（C）=（1+x）n.

棋盤2 R（C）=∑ m k=0 C（m，k）p（n，k）xk（m，n為正整數(shù)且m≤n）.

證明 棋盤2是一個(gè)n×m的規(guī)則棋盤，可先從m列中選取其中的k列布放棋子，有C（m，k）種方法，然后，第1個(gè)棋子有n種布局方法，第2個(gè)棋子有n-1種，直到第k個(gè)棋子有n-k+1種.從而rk（C）=C（m，k）n·（n-1）…（n-k+1）=C（m，k）P（n，k），故由棋盤多項(xiàng)式的概念可得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為正整數(shù)且b≥2）.

證明 應(yīng)用關(guān)鍵點(diǎn)遞歸法，前后選擇第1行第a+1列和第b行第a+1列的格子應(yīng)用性質(zhì)2，便得到棋盤3的棋盤多項(xiàng)式.

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.

四、結(jié)束語(yǔ)

本文對(duì)棋盤多項(xiàng)式的關(guān)鍵點(diǎn)遞歸法進(jìn)行分析，并得到三種特殊棋盤的棋盤多項(xiàng)式，方便人們計(jì)算時(shí)使用.然而，在實(shí)際的應(yīng)用過(guò)程中，人們還會(huì)遇到很多特殊的棋盤和具有特殊規(guī)律的棋盤多項(xiàng)式.若能加以總結(jié)歸納，勢(shì)必方便人們使用棋盤多項(xiàng)式解決實(shí)際問(wèn)題.

【參考文獻(xiàn)】

[1]牛立新，王功明，李洪淇，劉旭敏.棋盤多項(xiàng)式生成算法及其在禁位排列中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2006（10）：91-93.

[2]顧永跟.棋盤多項(xiàng)式在圖論中的應(yīng)用及其求解算法[J].湖州師專學(xué)報(bào)，1999，21（5）：44-50.

[3]趙澤茂，許彪.禁位排列問(wèn)題[J].河海大學(xué)常州分校學(xué)報(bào)，2000，41（2）：31-35.

[4]宋傳寧，邱懿.棋盤多項(xiàng)式的應(yīng)用[J].上海師范大學(xué)學(xué)報(bào)（自然科學(xué)版），1999，28（4）：31-34.

[5]李有梅，李素珍.棋盤多項(xiàng)式與夫妻分座問(wèn)題[J].山西大學(xué)學(xué)報(bào)（自然科學(xué)版），1997，20（4）：389-395.

[6]盧開(kāi)澄，盧華明.組合數(shù)學(xué)（第4版）[M].北京：清華大學(xué)出版社，2006.