矩形棋盘的多米诺覆盖方法数

本月的每月一讲中,我们将要深入讨论一个代数图论(Algebraic Graph Theory)当中有名的问题:

矩形棋盘的多米诺覆盖方法数

Number of Domino Tiling in Rectangular Chessboard

鉴于笔者水平有限,一些严格的图论语言无法翻译成中文,所以本文中一些定义和语言我们沿用2021年由剑桥大学出版的组合数学教材叙述方式。文中所有定理和引理读者都可在阅读时先尝试自行证明,再看文中的证明,分析两者的区别。本文中的情形适合初学者,而一般情形适合有一定代数、图论基础的读者,总体而言我们的文章基于Kasteleyn教授和Carnegie Mellon University 的 Brendan W. Sulliva教授的工作(感谢!)。

下面,让我们开始吧!

 

首先,我们简单地给一些定义,考虑一个的矩形棋盘和若干可任意旋转翻折的多米诺骨牌:

Definition

每月一讲:矩形棋盘的多米诺覆盖方法数

Example

每月一讲:矩形棋盘的多米诺覆盖方法数

每月一讲:矩形棋盘的多米诺覆盖方法数

Fact

每月一讲:矩形棋盘的多米诺覆盖方法数

Proof

每月一讲:矩形棋盘的多米诺覆盖方法数

 

Example

每月一讲:矩形棋盘的多米诺覆盖方法数

每月一讲:矩形棋盘的多米诺覆盖方法数

 

每月一讲:矩形棋盘的多米诺覆盖方法数

每月一讲:矩形棋盘的多米诺覆盖方法数

  Special Case: How many ways can one cover a 3 x n chessboard with dominoes?

Solution

每月一讲:矩形棋盘的多米诺覆盖方法数

每月一讲:矩形棋盘的多米诺覆盖方法数

每月一讲:矩形棋盘的多米诺覆盖方法数

 到此,一个自然的问题是,我们能否把这样的方法推广到一般的chessboard上。

 

事实上,如果记chessboard的Tiling 方法数,只要命m=4就容易发现,T(4,4) 的递推是个非常难以计算的式子:

每月一讲:矩形棋盘的多米诺覆盖方法数

尽管许多数学问题都可以用类推的思想,但很遗憾的是,Domino Tiling并不属于此类,因此我们要使用图论的方法得到其一般情况的解答。这个问题最早是由 Temperley & Fisher (1961) 和 Kasteleyn (1961) 分别独立解决的,这几位数学家都对于图论做出了很多贡献。

下面,我们将要使用图论技术,将这个问题首先抽象为一个平面图,再利用邻接矩阵(adjacency matrix)把它完全转为高等代数问题。此方法最基础的思想是:一个Domino Tiling 唯一对应一个chessboard 的underlying grid graph 的perfect matching。换句话说:只要确定哪些方块是被同一块骨牌覆盖的,也就确定了一个Domino Tiling,这意味着我们只要“恰当地”归类chessboard上的所有方块使得这样的归类方法的确是个tiling。

我们以一个具体的例子来阐述图论抽象操作是如何完成的:

STEPI:

把一个chessboard中的每个小方块抽象为一个顶点(vertex),如果两个小方块相邻(也即他们至少有一条公共边),则在它们之间连一条边(edge),这样的结果我们称为一个underlying grid graph:

每月一讲:矩形棋盘的多米诺覆盖方法数

STEPII:

我们把一个Domino Tiling看成是对于underlying grid graph中的edge的一种选取,目标是要覆盖顶点集(vertex set)

每月一讲:矩形棋盘的多米诺覆盖方法数

用图论术语来说,这就是个perfect matching

Definition

每月一讲:矩形棋盘的多米诺覆盖方法数

Example

每月一讲:矩形棋盘的多米诺覆盖方法数

Note

每月一讲:矩形棋盘的多米诺覆盖方法数

Fact

每月一讲:矩形棋盘的多米诺覆盖方法数

每月一讲:矩形棋盘的多米诺覆盖方法数

Note

每月一讲:矩形棋盘的多米诺覆盖方法数

 

Definition

每月一讲:矩形棋盘的多米诺覆盖方法数

Example

每月一讲:矩形棋盘的多米诺覆盖方法数

 

Example

每月一讲:矩形棋盘的多米诺覆盖方法数

 

Example

每月一讲:矩形棋盘的多米诺覆盖方法数

每月一讲:矩形棋盘的多米诺覆盖方法数

Note

每月一讲:矩形棋盘的多米诺覆盖方法数

 

每月一讲:矩形棋盘的多米诺覆盖方法数

 

Definition

每月一讲:矩形棋盘的多米诺覆盖方法数

这个处理的方法,我们称之为signing:

Definition

每月一讲:矩形棋盘的多米诺覆盖方法数

Example

每月一讲:矩形棋盘的多米诺覆盖方法数

下面,我们将要证明一个定理,先给一个不太严格的叙述:

Theorem

每月一讲:矩形棋盘的多米诺覆盖方法数

Definition

每月一讲:矩形棋盘的多米诺覆盖方法数

Definition

每月一讲:矩形棋盘的多米诺覆盖方法数

Definition

每月一讲:矩形棋盘的多米诺覆盖方法数

Definition

每月一讲:矩形棋盘的多米诺覆盖方法数

 

我们的grid graph 是2-connected的,可以不严格地由下图示意:

每月一讲:矩形棋盘的多米诺覆盖方法数

这个定理的叙述,现在可以很严格了:

Theorem

每月一讲:矩形棋盘的多米诺覆盖方法数

Note

每月一讲:矩形棋盘的多米诺覆盖方法数

Corollary

每月一讲:矩形棋盘的多米诺覆盖方法数

 

Definition

每月一讲:矩形棋盘的多米诺覆盖方法数

Example

每月一讲:矩形棋盘的多米诺覆盖方法数

 

Definition

每月一讲:矩形棋盘的多米诺覆盖方法数

Example

每月一讲:矩形棋盘的多米诺覆盖方法数

这样,我们就可以给出Lemma1了:

Lemma1

每月一讲:矩形棋盘的多米诺覆盖方法数

Proof Strategy

每月一讲:矩形棋盘的多米诺覆盖方法数

Proof

每月一讲:矩形棋盘的多米诺覆盖方法数

 

每月一讲:矩形棋盘的多米诺覆盖方法数

为此,我们先证明如下claim:

Claim

每月一讲:矩形棋盘的多米诺覆盖方法数

Proof

每月一讲:矩形棋盘的多米诺覆盖方法数

 

每月一讲:矩形棋盘的多米诺覆盖方法数

 

每月一讲:矩形棋盘的多米诺覆盖方法数

每月一讲:矩形棋盘的多米诺覆盖方法数

每月一讲:矩形棋盘的多米诺覆盖方法数

 

每月一讲:矩形棋盘的多米诺覆盖方法数

 

每月一讲:矩形棋盘的多米诺覆盖方法数

 

每月一讲:矩形棋盘的多米诺覆盖方法数

Lemma1从而得证。

关于第二个引理,我们将引入平面图(planar graph)中很重要的概念和定理,但篇幅有限,我们将不严格地介绍:

平面图的planar drawing就是一个把它画在平面的方法,每个固定的画法都会有vertex, edge,和faces(面),如右图有9个inner faces和一个outer faces。关于这些数量,Euler有一个著名的定理

每月一讲:矩形棋盘的多米诺覆盖方法数

有了这些准备工作,我们来介绍Lemma2。

Lemma2

每月一讲:矩形棋盘的多米诺覆盖方法数

每月一讲:矩形棋盘的多米诺覆盖方法数

Proof

每月一讲:矩形棋盘的多米诺覆盖方法数

 

每月一讲:矩形棋盘的多米诺覆盖方法数

立刻可知C也是properly-signed,由Lemma1知结论成立!

 

经历了很长的引理和定理证明,也仅仅得到了T(m,n)的计算是多项式时间内的,真正得到它的公式还需要一些别的技术,这不是我们的重点。最后,让我们来看一下T(m,n)的形式:

每月一讲:矩形棋盘的多米诺覆盖方法数

【竞赛报名/项目咨询请加微信:mollywei007】

上一篇

递推方法解决AMC组合数学或概率论问题

下一篇

从斐波那契数列看线性递推数列通项公式的求法

你也可能喜欢

  • 暂无相关文章!

评论已经被关闭。

插入图片
返回顶部