ドミノタイリング

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
四方形のドミノタイリング

ユークリッド平面上のある領域のドミノタイリング(domino tiling)とは、右の図のようにドミノで領域を埋め尽すことである。同じことであるが、ドミノタイリングは、各々のドミノの中心に頂点として隣合うドミノの 2つの頂点を結ぶことで形成される格子グラフ英語版(grid graph)のマッチングのことでもある。モノマー、ダイマー、ポリマーと呼ぶように、2つの原子が繋がったという意味であるユークリッド平面上の(あるいは、トーラス 上の)ダイマーモデル(Dimer model)は、多角形分割英語版(polygon division)をもたらすモデルであり、完全マッチングであるダイマーモデルは、ドミノタイリングと同義である。

高さ函数[編集]

2次元の正方形の格子上のタイリングのクラスに対し、格子のノードへ整数を割り当てる高さ函数を定義することができる。例えば、チェスボード(格子を黒と白の市松模様とする)を描いて、高さ 0 を持つノード を固定すると、どのノードに対しても からの経路が存在する。この経路上で、各々のノード (つまり、四方形の頂点)の高さを、 から への経路の右側の四方形が黒であれば、前のノード に 1 をプラスした値とする。そうでなければ、1 をマイナスした値とする。

さらに詳しくは、Kenyon & Okounkov (2005)に記載がある。

サーストンの高さ条件[編集]

ウィリアム・サーストン(William Thurston)は、1990年に平面内の単連結な領域が、単位四方形の組(ドミノ)によりドミノタイリングとして形成されるか否かを決定できることを著した。彼は、3次元の整数格子英語版(integer lattice)の中の点 (x,y,z) を頂点として持つような無向グラフを作った。そこでは各々の点が 4つの近傍に連結していて、x+y が偶数であれば、(x,y,z) は (x+1,y,z+1), (x-1,y,z+1), (x,y+1,z-1), (x,y-1,z-1) と連結し、一方、x+y が奇数であれば、(x,y,z) は (x+1,y,z-1), (x-1,y,z-1), (x,y+1,z+1), (x,y-1,z+1) と連結している。この領域の境界は、(x,y) 平面の中の整数の点の列として見なすと、この一意に 3次元グラフ英語版(three-dimensional graph)の中の経路へ(一度、初期の高さを決めると)持ち上げることができる。この領域がタイリング可能であるための必要条件は、この経路が 3次元で単純な閉曲線を形成することを除いて閉じている必要がある。しかし、この条件だけでは充分でない。境界の経路のより注意深く解析して、サーストンは必要かつ充分な領域のタイリングの可能性の判定条件を与えた。

領域のタイリングの数[編集]

8×8 マスのドミノタイリングで、ドミノの長辺と長辺が接するペアの数が最小となるもの(中央に一組ある)。この並べ方は、8×8 マスでのの敷き詰め方としても有効であり、内部のどの点も4つのドミノが接することがない。

の長方形を 個のドミノで埋め尽くす方法が何通りあるかの個数の公式は、独立に、Temperley & Fisher (1961)Kasteleyn (1961) により計算され、

として得られた。

この特別な場合として、-長方形のタイリングの方法が何通りあるかという問題がある。この数は、フィボナッチ数列n-番目の数であるオンライン整数列大辞典の数列 A000045 (Klarner & Pollack 1980)。

他の特別な場合として、m = n = 0, 2, 4, 6, 8, 10, 12, ... であるようなケースがある。

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... オンライン整数列大辞典の数列 A004003.

これらの何通りあるかという数は、固有値が明確に分かる 個の交代行列パフィアンとして記述することにより、計算することが可能となる。このテクニックは多くの数学的に関連する問題へ適用することが可能である。例えば、統計力学でのダイマー-ダイマー相関函数英語版(dimer-dimer correlator function)の古典的 2次元の計算がある。

領域のタイリングの数は境界条件に対して非常に敏感で、一見たいしたことのない形の変化であっても、その数が劇的に変化する場合がある。わかりやすい例に、位数 nアステカダイアモンド英語版(Aztec diamond) があり、このタイリングの数は、2(n + 1)n/2 である。一方、位数が同じ n でも、中央の長い列が2列ではなく3列に 拡張されたアステカダイアモンド になると、タイリングの数はnテトレーションから大きく減少し、指数的な数であるデラノイ数英語版(Delannoy number) D(n,n) に等しくなる。また、中央列が1列である 縮小されたアステカダイアモンドは、たったひとつのタイリングしか持たない。

参照項目[編集]

  • 統計力学
  • ガウス自由場英語版(Gaussian free field)、一般的な状況下で、高さ函数のスケール極限(つまり、大きなアステカダイアモンドの内接円板の内部)
  • 多重チェスボート問題英語版(Mutilated chessboard problem)、チェスボートの 62個の正方形のドミノタイリングに関するパズル
  • 、日本式の部屋の床のタイリングに使われるドミノの形をした床のマット、並べ方にあるルールを持っている。

参考文献[編集]