ドミノタイリング

提供: testwiki
ナビゲーションに移動 検索に移動

テンプレート:要改訳

四方形のドミノタイリング

ユークリッド平面上のある領域のドミノタイリング(domino tiling)とは、右の図のようにドミノで領域を埋め尽すことである。同じことであるが、ドミノタイリングは、各々のドミノの中心に頂点として隣合うドミノの 2つの頂点を結ぶことで形成されるテンプレート:仮リンク(grid graph)のマッチングのことでもある。モノマー、ダイマー、ポリマーと呼ぶように、2つの原子が繋がったという意味であるユークリッド平面上の（あるいは、トーラス ℝ2/ℤ2 上の）ダイマーモデル（Dimer model，双体模型）は、テンプレート:仮リンク(polygon division)をもたらすモデルであり、完全マッチングであるダイマーモデルは、ドミノタイリングと同義である。

高さ函数

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

さらに詳しくは、テンプレート:Harvtxtに記載がある。

サーストンの高さ条件

ウィリアム・サーストン(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) 平面の中の整数の点の列として見なすと、この一意に テンプレート:仮リンク(three-dimensional graph)の中の経路へ（一度、初期の高さを決めると）持ち上げることができる。この領域がタイリング可能であるための必要条件は、この経路が 3次元で単純な閉曲線を形成することを除いて閉じている必要がある。しかし、この条件だけでは充分でない。境界の経路のより注意深く解析して、サーストンは必要かつ充分な領域のタイリングの可能性の判定条件を与えた。

領域のタイリングの数

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

m×n の長方形を mn2 個のドミノで埋め尽くす方法が何通りあるかの個数の公式は、独立に、テンプレート:Harvtxt と テンプレート:Harvtxt により計算され、

∏j=1⌈m2⌉∏k=1⌈n2⌉(4cos2πjm+1+4cos2πkn+1)

として得られた。

この特別な場合として、2×n-長方形のタイリングの方法が何通りあるかという問題がある。この数は、フィボナッチ数列の n-番目の数であるテンプレート:OEIS テンプレート:Harv。

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

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... テンプレート:OEIS.

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

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

  • 位数 4 のアステカダイアモンド、1024 種類のドミノタイリングを持つ
    位数 4 のアステカダイアモンド、1024 種類のドミノタイリングを持つ
  • 位数 4 のアステカダイアモンドにおけるドミノタイリングの一例
    位数 4 のアステカダイアモンドにおけるドミノタイリングの一例

参照項目

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

参考文献

「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=ドミノタイリング&oldid=10641」から取得