4Xn棋盤的染色計(jì)數(shù)問題分析

張上偉,吳 康

(華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,廣東 廣州 510631)

0 預(yù)備知識(shí)

為了方便討論4Xn棋盤的染色計(jì)數(shù)問題,本文給出了以下三個(gè)引理:

引理1.1 設(shè){an}n≥0和 {bn}n≥0是兩個(gè)數(shù)列,s是非負(fù)整數(shù),如果對(duì)任意的不小于s的整數(shù)n,都有,則對(duì)任意的不小于s的整數(shù)n,都有

引理1.2 以gm(n)表示用m(m≥2)種顏色去染2Xn棋盤,使得相鄰格子異色的染色方法數(shù),則gm(n)=m(m-1)(m2-3m+3)n-1.

以hm(n)表示用m(m≥3)種顏色去染3Xn棋盤,使得相鄰格子異色且每一列格子中無相同顏色的染色方法數(shù),則hm(n)=m(m-1)(m-2)[(m-1)(m-2)+(m-3)(m2-4m+5)]n-1.

引理1.3 以gm(n)表示m(m≥2)用種顏色去染2Xn棋盤,使得相鄰格子異色,且每種顏色至少使用一次的染色方法數(shù),則

以hm(n)表示用m(m≥3)種顏色去染3Xn棋盤,使得相鄰格子異色,每一列格子中無相同顏色且每種顏色至少使用一次的染色方法數(shù),則

1 4Xn棋盤的染色計(jì)數(shù)問題分析

定理2.1 以fm(n)表示用m(m≥4)種顏色去染4Xn棋盤,使得相鄰格子異色且每一列格子中無相同顏色的染色方法數(shù),則

證明:利用加法原則和乘法原則證明計(jì)數(shù)公式.可分n個(gè)步驟,每個(gè)步驟對(duì)棋盤的一列格子進(jìn)行染色.如圖1.

圖1 4Xn棋盤

步驟1:對(duì)棋盤的第1列格子進(jìn)行染色,因?yàn)橄噜徃褡赢惿颐恳涣懈褡又袩o相同顏色,所以第1列格子的染色方法數(shù)為m(m-1)(m-2)(m-3).

步驟2:對(duì)棋盤的第2列格子進(jìn)行染色,可分如下兩類.

(一)e與b同色,屬于此類的染色方法數(shù)可分為如下兩類.

(1)f與c同色.屬于此類的染色方法數(shù)可分為如下兩類.

a)g與d同色.染色方法數(shù)為(m-3).

b)g與d異色.染色方法數(shù)為(m-3)(m-4).

(2)f與c異色.屬于此類的染色方法數(shù)可分為如下三類.

a)f與d同色.染色方法數(shù)為(m-3)(m-3).

b)f與d異色且g與d同色.染色方法數(shù)為(m-3)(m-3).

c)f與d異色且g與d異色.染色方法數(shù)為(m-3)(m-4)(m-4).

(二)e與b異色,屬于此類的染色方法數(shù)可分為如下兩類.

(1)e與c同色.屬于此類的染色方法數(shù)可分為如下三類.

a)f與d同色.染色方法數(shù)為(m-2)(m-3).

b)f與d異色且g與d同色.染色方法數(shù)為(m-3)(m-3).

c)f與d異色且g與d異色.染色方法數(shù)為(m-3)(m-3)(m-4)..

(2)e與c異色.屬于此類的染色方法數(shù)可分為如下七類.

a)e與d同色且f與c同色.染色方法數(shù)為(m-2)(m-3).

b)e與d同色且f與c異色.染色方法數(shù)為(m-3)(m-3)(m-3).

c)e與d異色且f與c同色且g與d同色.染色方法數(shù)為(m-4)(m-3).

d)e與d異色且f與c同色且g與d異色.染色方法數(shù)為(m-4)(m-3)(m-4).

e)e與d異色且f與c異色且f與d同色.染色方法數(shù)為(m-4)(m-3)(m-3).

f)e與d異色且f與c異色且f與d異色且g與d同色.染色方法數(shù)為

(m-4)(m-4)(m-3).

g)e與d異色且f與c異色且f與d異色且g與d異色.染色方法數(shù)為

(m-4)(m-4)(m-4)(m-4).

由加法原則可知,第2列格子的染色方法數(shù)為以上染色方法數(shù)的總和,為

(m-3)(6m2-37m+61)+(m-4)4.

再考慮第3列直至第n列,其染色方法數(shù)與考慮第2列格子的染色方法數(shù)類同,每一列格子的染色方法數(shù)均為(m-3)(6m2-37m+61)+(m-4)4.

再根據(jù)乘法原則可知,fm(n)=m(m-1)(m-2)(m-3)[(m-3)(6m2-37m+61)+(m-4)4]n-1.

定理2.2以fm′(n)表示用m(m≥4)種顏色去染4Xn棋盤,使得相鄰格子異色,每一列格子中無相同顏色且每種顏色至少使用一次的染色方法數(shù),則

證明:由定理2.1知,用m(m≥4)種顏色去染4Xn棋盤,使得相鄰格子異色且每一列格子中無相同顏色的染色方法數(shù)為

由引理1.3,可得

[1]曹汝成.組合數(shù)學(xué)[M].廣州:華南理工大學(xué)出版社,2000.

[2]楊勝良.組合數(shù)學(xué)引論[M].蘭州:蘭州大學(xué)出版社,2006.

[3]顧紅俏.關(guān)于棋盤的染色計(jì)數(shù)公式[J].新疆師范大學(xué)學(xué)報(bào):自然科學(xué)版,2007(03):90-92.

[4]柳柏濂,吳康.競(jìng)賽數(shù)學(xué)的原理和方法[M].廣州:廣東高等教育出版社,2005.

[5]熊斌.棋盤的染色問題[J].中等數(shù)學(xué),1991(01):25-28.