矩形棋盘的多米诺覆盖方法数
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】
