ドミノタイル
8×8の正方形のドミノタイル

幾何学において、ユークリッド平面上の領域をドミノタイルで敷き詰める（ドミノタイルを敷き詰める）とは、2つの単位正方形の辺が接する集合体であるドミノによって領域を敷き詰めることである。同様に、ドミノタイルは、領域内の各正方形の中心に頂点を置き、隣接する正方形に対応する2つの頂点を結んで形成されるグリッドグラフにおける完全マッチングである。

高さ関数

2次元の規則的なグリッド上のタイリングのいくつかのクラスでは、グリッドの頂点に整数を関連付ける高さ関数を定義できます。例えば、チェス盤を描き、高さ0のノードを固定すると、任意のノードからそのノードへのパスが存在します。このパス上で、各ノード（つまり、マス目の角）の高さを、パスの右側のマス目が黒の場合は前のノードの高さに1を加算し、黒の場合は1を減算したものと定義します。 あ0{\displaystyle A_{0}}あ0{\displaystyle A_{0}}あn+1{\displaystyle A_{n+1}}あn{\displaystyle A_{n}}あn{\displaystyle A_{n}}あn+1{\displaystyle A_{n+1}}

詳細については、Kenyon & Okounkov (2005)を参照してください。

サーストンの身長制限

ウィリアム・サーストン （1990年）は、平面上の単位正方形の結合として形成される単連結領域がドミノタイルであるかどうかを判定するテストについて説明しています。彼は、3 次元整数格子内の点 ( x、y、z ) を頂点とする無向グラフを形成します。ここで、各点は 4 つの近傍点に接続されます。 x + y が偶数の場合、 ( x 、 y 、 z ) は、 ( 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 、 y + 1  、z +  1)、 ( x、y  − 1、z  + 1)に接続されます。領域の境界は、( x , y )平面上の整数点の列として捉えられ、（開始高さを選べば）この3次元グラフ上のパスへと一意に上昇する。この領域がタイル化可能であるための必要条件は、このパスが3次元において単純な閉曲線を形成するように閉じていることであるが、この条件だけでは十分ではない。サーストンは境界パスをより慎重に分析することで、領域のタイル化可能性に関する必要条件であると同時に十分条件でもある基準を与えた。

領域のタイリングを数える

8×8の正方形に、長辺同士のペアを最小限の数（中央に1ペア）で並べたドミノの配置。この配置は、4つのドミノが内部で接することなく、8×8の正方形に畳敷きとしても有効である。

長方形をドミノで覆う方法の数は、Temperley & Fisher (1961)とKasteleyn (1961)によって独立に計算され、 ( OEISのシーケンスA099390 )で与えられます 。 メートル×n{\displaystyle m\times n}メートルn2{\displaystyle {\frac {mn}{2}}}∏j＝1⌈メートル2⌉∏け＝1⌈n2⌉（4コス2⁡πjメートル+1+4コス2⁡πけn+1）{\displaystyle \prod _{j=1}^{\lceil {\frac {m}{2}}\rceil }\prod _{k=1}^{\lceil {\frac {n}{2}}\rceil }\left(4\cos ^{2}{\frac {\pi j}{m+1}}+4\cos ^{2}{\frac {\pi k}{n+1}}\right)}

mとn が両方とも奇数の場合、式はドミノのタイルの可能な数が 0 になるように正しく簡約されます。

長方形をn個のドミノで並べると特別なケースが発生します。数列はフィボナッチ数列に簡約されます。[ 1 ]2×n{\displaystyle 2\times n}

もう一つの特別なケースは、 m = n = 0, 2, 4, 6, 8, 10, 12, ... の正方形の場合です。

1、2、36、6728、12988816、258584046368、53060477521960000、...（OEISのシーケンスA004003）。

これらの数は、固有値が明示的に求められる歪対称行列のパフィアンとして書き表すことで求めることができます。この手法は、統計力学における古典的な2次元ダイマー-ダイマー相関関数の計算など、数学関連の多くの分野に応用できます。 メートルn×メートルn{\displaystyle mn\times mn}

領域のタイリング数は境界条件に非常に敏感で、領域の形状がわずかに変化しただけでも劇的に変化することがあります。これは、 n次のアステカ ダイヤモンドのタイリング数で示されます。この場合、タイリング数は 2 ( n  + 1) n /2です。これを、中央の長い列が 2 列ではなく 3 列であるn次の「拡大アステカ ダイヤモンド」に置き換えると、タイリング数ははるかに小さい数 D( n , n )、つまりデラノア数にまで減少します。これは、 nの増加が超指数関数的ではなく指数関数的であるだけです。 n 次の長い列が 1 列だけの「縮小アステカ ダイヤモンド」の場合、タイリングは 1 つだけです。

  • 1024個のドミノタイルを持つ、4次のアステカダイヤモンド
    1024個のドミノタイルを持つ、4次のアステカダイヤモンド
  • 可能なタイリングの1つ
    可能なタイリングの1つ

畳

畳はドミノ（1x2の長方形）の形をした日本の床マットです。部屋をタイル張りするのに使われますが、その敷き方には特別なルールがあります。特に、一般的に畳が3枚接する接合部は縁起が良く、4枚接する接合部は縁起が悪いとされているため、どの角も3枚接する畳が正しい畳の敷き方です。[ 2 ]不規則な部屋に、3枚接する畳で角をタイル張りする問題はNP完全です。[ 3 ]

統計物理学への応用

周期的ドミノタイリングと、 2次元周期格子上の完全フラストレート・イジング模型の基底状態構成との間には、 1対1の対応関係がある。 [ 4 ]基底状態において、スピン模型の各プラケットは、正確に1つのフラストレート相互作用を含まなければならない。したがって、双対格子から見ると、各フラストレート・エッジは、格子全体に広がり、かつ重なり合わない1x2の長方形、すなわち双対格子のドミノタイリングで「覆われる」必要がある。

参照

注記

  1. ^クラナー＆ポラック 1980 .
  2. ^ラスキー＆ウッドコック 2009 .
  3. ^エリックソン＆ラスキー 2013 .
  4. ^バラホナ (1982) .

参考文献

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Domino_tiling&oldid=1315061111」から取得