矩形棋盘上完全覆盖的计数

梁登星, 王 娟

(成都理工大学 管理科学学院, 四川 成都 610059)

矩形棋盘上完全覆盖的计数

梁登星, 王 娟

(成都理工大学 管理科学学院, 四川 成都 610059)

研究矩形棋盘上的1×2骨牌覆盖问题,通过生成函数的方法,分别给出3×n,4×n矩形棋盘上的覆盖数N(3,n),N(4,n)的生成函数.

完全覆盖; 递推关系; 生成函数

称两边长分别为m,n的矩形为m×n矩形棋盘.m×n棋盘T上的一个完全覆盖是指,用1×2的骨牌对T进行不重复不遗漏的覆盖[1,2].记m×n棋盘上完全覆盖的方法数为N(m,n).本文着重研究N(3,n)和N(4,n)的一些组合性质.

定理1N(3,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．

证明初始条件显然成立.

设缺角3×n棋盘的覆盖数为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)的生成函数为

证明设N(3,n)的生成函数为

则由定理1,计算可知

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

考虑A(x)的泰勒展开式,我们有

其中〈x〉表示距离实数x最近的整数．

因此

另一方面,由于

定理的后半部分成立．

类似与以上的分析过程,我们来分析N(4,n)的计数问题.

定理4N(4,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),其覆盖数为f(n);记缺角上相邻两个格子的4×n的棋盘为X2(n)(图6),其覆盖数为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. 组合学导论[M].//李盘林, 王天明.译. 武昌: 华中理工大学出版社,1982.

[2] 曹汝成. 组合数学[M]. 广州: 华南理工大学出版社, 2005.

[责任编辑：李春红]

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空间分析.