矩形棋盤的多米諾覆蓋方法數

本月的每月一講中，我們將要深入討論一個代數圖論(Algebraic Graph Theory)當中有名的問題：

矩形棋盤的多米諾覆蓋方法數

Number of Domino Tiling in Rectangular Chessboard

鑒於(yu) 筆者水平有限，一些嚴(yan) 格的圖論語言無法翻譯成中文，所以本文中一些定義(yi) 和語言我們(men) 沿用2021年由劍橋大學出版的組合數學教材敘述方式。文中所有定理和引理讀者都可在閱讀時先嚐試自行證明，再看文中的證明，分析兩(liang) 者的區別。本文中的情形適合初學者，而一般情形適合有一定代數、圖論基礎的讀者，總體(ti) 而言我們(men) 的文章基於(yu) Kasteleyn教授和Carnegie Mellon University 的 Brendan W. Sulliva教授的工作（感謝！）。

下麵，讓我們(men) 開始吧！

 

首先，我們(men) 簡單地給一些定義(yi) ，考慮一個(ge) 的矩形棋盤和若幹可任意旋轉翻折的多米諾骨牌：

Definition

Example

Fact

Proof

 

Example

 

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

Solution

 到此，一個(ge) 自然的問題是，我們(men) 能否把這樣的方法推廣到一般的chessboard上。

 

事實上，如果記chessboard的Tiling 方法數，隻要命m=4就容易發現，T(4,4) 的遞推是個(ge) 非常難以計算的式子：

盡管許多數學問題都可以用類推的思想，但很遺憾的是，Domino Tiling並不屬於(yu) 此類，因此我們(men) 要使用圖論的方法得到其一般情況的解答。這個(ge) 問題最早是由 Temperley & Fisher (1961) 和 Kasteleyn (1961) 分別獨立解決(jue) 的，這幾位數學家都對於(yu) 圖論做出了很多貢獻。

下麵，我們(men) 將要使用圖論技術，將這個(ge) 問題首先抽象為(wei) 一個(ge) 平麵圖，再利用鄰接矩陣(adjacency matrix)把它完全轉為(wei) 高等代數問題。此方法最基礎的思想是：一個(ge) Domino Tiling 唯一對應一個(ge) chessboard 的underlying grid graph 的perfect matching。換句話說：隻要確定哪些方塊是被同一塊骨牌覆蓋的，也就確定了一個(ge) Domino Tiling，這意味著我們(men) 隻要“恰當地”歸類chessboard上的所有方塊使得這樣的歸類方法的確是個(ge) tiling。

我們(men) 以一個(ge) 具體(ti) 的例子來闡述圖論抽象操作是如何完成的：

STEPI:

把一個(ge) chessboard中的每個(ge) 小方塊抽象為(wei) 一個(ge) 頂點(vertex)，如果兩(liang) 個(ge) 小方塊相鄰（也即他們(men) 至少有一條公共邊），則在它們(men) 之間連一條邊(edge)，這樣的結果我們(men) 稱為(wei) 一個(ge) underlying grid graph：

STEPII：

我們(men) 把一個(ge) Domino Tiling看成是對於(yu) underlying grid graph中的edge的一種選取，目標是要覆蓋頂點集(vertex set)：

用圖論術語來說，這就是個(ge) perfect matching。

Definition

Example

Note

Fact

Note

 

Definition

Example

 

Example

 

Example

Note

 

 

Definition

這個(ge) 處理的方法，我們(men) 稱之為(wei) signing:

Definition

Example

下麵，我們(men) 將要證明一個(ge) 定理，先給一個(ge) 不太嚴(yan) 格的敘述：

Theorem

Definition

Definition

Definition

Definition

 

我們(men) 的grid graph 是2-connected的，可以不嚴(yan) 格地由下圖示意：

這個(ge) 定理的敘述，現在可以很嚴(yan) 格了：

Theorem

Note

Corollary

 

Definition

Example

 

Definition

Example

這樣，我們(men) 就可以給出Lemma1了：

Lemma1

Proof Strategy

Proof

 

為(wei) 此，我們(men) 先證明如下claim：

Claim

Proof

 

 

 

 

 

Lemma1從(cong) 而得證。

關(guan) 於(yu) 第二個(ge) 引理，我們(men) 將引入平麵圖(planar graph)中很重要的概念和定理，但篇幅有限，我們(men) 將不嚴(yan) 格地介紹：

平麵圖的planar drawing就是一個(ge) 把它畫在平麵的方法，每個(ge) 固定的畫法都會(hui) 有vertex, edge,和faces（麵），如右圖有9個(ge) inner faces和一個(ge) outer faces。關(guan) 於(yu) 這些數量，Euler有一個(ge) 著名的定理：

有了這些準備工作，我們(men) 來介紹Lemma2。

Lemma2

Proof

 

立刻可知C也是properly-signed，由Lemma1知結論成立！

 

經曆了很長的引理和定理證明，也僅(jin) 僅(jin) 得到了T(m,n)的計算是多項式時間內(nei) 的，真正得到它的公式還需要一些別的技術，這不是我們(men) 的重點。最後，讓我們(men) 來看一下T(m,n)的形式：