4Xn棋盤的染色計數問題分析

張上偉,吳 康

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

0 預備知識

為了方便討論4Xn棋盤的染色計數問題,本文給出了以下三個引理:

引理1.1 設{an}n≥0和 {bn}n≥0是兩個數列,s是非負整數,如果對任意的不小于s的整數n,都有,則對任意的不小于s的整數n,都有

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

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

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

1 4Xn棋盤的染色計數問題分析

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

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

圖1 4Xn棋盤

步驟1:對棋盤的第1列格子進行染色,因為相鄰格子異色且每一列格子中無相同顏色,所以第1列格子的染色方法數為m(m-1)(m-2)(m-3).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

再根據乘法原則可知,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棋盤,使得相鄰格子異色,每一列格子中無相同顏色且每種顏色至少使用一次的染色方法數,則

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

由引理1.3,可得

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

[2]楊勝良.組合數學引論[M].蘭州:蘭州大學出版社,2006.

[3]顧紅俏.關于棋盤的染色計數公式[J].新疆師范大學學報:自然科學版,2007(03):90-92.

[4]柳柏濂,吳康.競賽數學的原理和方法[M].廣州:廣東高等教育出版社,2005.

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