矩形棋盤上完全覆蓋的計數(shù)

梁登星, 王 娟

(成都理工大學(xué) 管理科學(xué)學(xué)院, 四川 成都 610059)

矩形棋盤上完全覆蓋的計數(shù)

梁登星, 王 娟

(成都理工大學(xué) 管理科學(xué)學(xué)院, 四川 成都 610059)

研究矩形棋盤上的1×2骨牌覆蓋問題,通過生成函數(shù)的方法,分別給出3×n,4×n矩形棋盤上的覆蓋數(shù)N(3,n),N(4,n)的生成函數(shù).

完全覆蓋; 遞推關(guān)系; 生成函數(shù)

稱兩邊長分別為m,n的矩形為m×n矩形棋盤.m×n棋盤T上的一個完全覆蓋是指,用1×2的骨牌對T進行不重復(fù)不遺漏的覆蓋[1,2].記m×n棋盤上完全覆蓋的方法數(shù)為N(m,n).本文著重研究N(3,n)和N(4,n)的一些組合性質(zhì).

定理1N(3,n)滿足遞推關(guān)系

N(3,n)=4·N(3,n-2)-4·N(3,n-4),

以及初始條件

N(3,2)=3,N(3,1)=N(3,3)=0,N(3,0)=1．

證明初始條件顯然成立.

設(shè)缺角3×n棋盤的覆蓋數(shù)為g(n),則易見g(1)=1.按3×n棋盤第一行的覆蓋方案分類,有以下三種情況:

情形1: 第一列的格子由三塊橫置的骨牌所覆蓋,如圖1所示,記此覆蓋方案集合為D1.則|D1|=N(3,n-2).

圖1 缺角3×n棋盤情形1的第一列的格子

圖2 缺角3×n棋盤情形2的第一列的格子

情形2: 第一列的格子由左上角的一塊橫置的骨牌和左下角的一塊豎置的骨牌覆蓋,如圖2所示,記此覆蓋方案集合為D2.則|D2|=g(n-1).

情形3: 第一列的格子由左下角的一塊橫置的骨牌和左上角的一塊豎置的骨牌覆蓋,記此覆蓋方案集合為D3.由對稱性知,|D3|=|D2|=g(n-1).

由此可知

N(3,n)=|D1|+|D2|+|D3|=N(3,n-2)+2·g(n-1)

(1)

再分析缺角3×n棋盤,對于缺角的一列,有以下2種覆蓋情況:

情形1: 缺角的列由兩塊橫置的骨牌覆蓋,如圖3所示,記此覆蓋方案集合為E1.則|E1|=g(n-2).

情形2: 缺角的列由一塊豎置的骨牌覆蓋,如圖4所示,記此覆蓋方案集合為E2.則|E2|=N(3,n-1).

圖3 缺角3×n棋盤情形1缺角的列

圖4 缺角3×n棋盤情形2缺角的列

因此有

g(n)=N(3,n-1)+g(n-2)

(2)

由(1)得,

代入(2),整理得

N(3,n+1)=4·N(3,n-1)-4·N(3,n-3)

即N(3,n)=4·N(3,n-2)-4·N(3,n-4).

定理2N(3,n)的生成函數(shù)為

證明設(shè)N(3,n)的生成函數(shù)為

則由定理1,計算可知

(1-4x2+x4)·A(x)=1-x2,

考慮A(x)的泰勒展開式,我們有

其中〈x〉表示距離實數(shù)x最近的整數(shù)．

因此

另一方面,由于

定理的后半部分成立．

類似與以上的分析過程,我們來分析N(4,n)的計數(shù)問題.

定理4N(4,n)滿足遞推關(guān)系

N(4,n)=N(4,n-1)+5·N(4,n-2)+N(4,n-3)-N(4,n-4)

以及初始條件

N(4,0)=1,N(4,1)=1,N(4,2)=5,N(4,3)=8．

證明初始條件顯然正確.

記缺兩個角的4×n的棋盤為X1(n)(圖5),其覆蓋數(shù)為f(n);記缺角上相鄰兩個格子的4×n的棋盤為X2(n)(圖6),其覆蓋數(shù)為g(n).

圖5 缺兩個角的4×8矩陣

圖6 缺角上相鄰兩格的4×8矩陣

類似于定理1的分析,有

N(4,n)=N(4,n-1)+2·g(n-1)+f(n-1)+N(4,n-2)f(n)=N(4,n-1)+f(n-2)

g(n)=N(4,n-1)+g(n-1)

整理,消去f(n),g(n),得

N(4,n)=N(4,n-1)+5·N(4,n-2)+(4,n-3)-N(4,n-4).

計算可得,

[1] Brualdi R A. 組合學(xué)導(dǎo)論[M].//李盤林, 王天明.譯. 武昌: 華中理工大學(xué)出版社,1982.

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

[責(zé)任編輯：李春紅]

EnumerationofPerfectCoverintheRectangularChessboard

LIANG Deng-xing, WANG Juan

(College of Management Science, Chengdu University of Technology, Chengdu Sichuan 610059, China)

Based on the method of generating function theory, the paper analyzes the problem of perfect cover of rectangular chessboard and gets the generating function ofN(3，n) andN(4，n).

perfect cover; recurrence relations; generating function

O157

A

1671-6876(2012)02-0134-03

2012-04-05

梁登星(1986-), 女, 河北張家口人, 碩士研究生, 研究方向為GIS空間分析.