ドミノタイリングの数え上げ（その１）

ドミノタイリングとは

ドミノタイリング (Wikipedia) あるように、

領域のドミノタイリング(domino tiling)とは、図のようにドミノで領域を埋め尽すことである。

ここでは$N*N$の正方形をドミノタイリングで埋め尽くす方法の数を求める、すなわち OEIS A004003: Number of domino tilings (or dimer coverings) of a 2n X 2n squareをプログラム的に求めることを目的とします。

ドミノタイリングと格子グラフのマッチング問題

Wikiにもあるようにドミノタイリングと格子グラフのマッチング問題は同義であるので、以下のように格子グラフの頂点が1対1にマッチングする問題に置き換えて考えます。

格子グラフの1対1にマッチング

この格子グラフの図で各々の正方形のタイルに注目すると、以下の4種類しかありません。従ってこれらのタイルをジグソーパズルの様に模様がつながるように埋める問題に置き換えられます。

タイル張り問題を考える

横１行のパターンを作る

問題を簡素化して２ｘNのタイル張り問題を考えます。タイルの横１行に注目すると以下の５つのパターンがあり、各タイルの上と下の辺のある無しを(1, 0)で表します。

#	横１行のパターン	上への辺	下への辺
1		(1,1)	(0,0)
2		(1,0)	(0,1)
3		(0,0)	(0,0)
4		(0,0)	(1,1)
5		(0,1)	(1,0)

これを使うと例えば #4 の行の下への辺は(1,1)なので、次の行は #1 しかない事が分かります。

この横１行の上下の辺パターンを作るコードです。上の辺から下の辺パターンを直接取り出せるようにDICT形式を使っています。

TILES = [(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)]

N = 2
from collections import defaultdict
ROWS = defaultdict(list)

def build1row(c, lnode, ulist, dlist):  # column, left node, up node list, down node list
	if c == N:
		if lnode == 0:
			ROWS[tuple(ulist)].append(tuple(dlist))
		return
	for (U, R, D, L) in TILES:
		if L == lnode:  # West == border
			build1row(c+1, R, ulist + [U], dlist + [D])

build1row(0, 0, [], [])  # Build Row data
for u, d in ROWS.items():
	print(f"# UP = {u}, DOWN = {d}")
# UP = (1, 1), DOWN = [(0, 0)]
# UP = (1, 0), DOWN = [(0, 1)]
# UP = (0, 0), DOWN = [(0, 0), (1, 1)]
# UP = (0, 1), DOWN = [(1, 0)]

組み合わせの数を積算して数える

このデータを元に各パターンの数を積算して行き、最後の行の下の辺パターンが(0,0)になっているものが答えとなります。N=2のときに2という答えが求まりました。

CNT = defaultdict(int)
tb_edge = tuple([0]*N)  # top or bottom edge (0,...,0)
CNT[tb_edge] = 1
for r in range(N):
	CNT2 = defaultdict(int)
	for ulist, dlist in ROWS.items():
		for d in dlist:
			CNT2[d] += CNT[ulist]
	CNT = deepcopy(CNT2)
# Answer: 2

実際N=2のときは以下の２通りが答えになります。

偶数Nに対して組み合わせの数を求める

後はNを変えてこのコードを走らせるだけです。OEIS A004003と同じ値が確認できました。

N	ドミノタイリングの数
2	2
4	36
6	6728
8	12988816
10	258584046368
12	53060477521960000
14	112202208776036178000000
16	2444888770250892795802079170816
18	548943583215388338077567813208427340288
20	1269984011256235834242602753102293934298576249856

N=4の時の36個のパターン

組み合わせの数だけでは味気ないので、N=4の時の36個のパターンをすべて表示してみました。

次回のドミノタイリングの数え上げ（その２）ではこのコードはそのままで、TILESのデータを変えるだけで他の問題を解くことが出来ることを示したいと思います。

（開発環境：Google Colab）