アステカダイヤモンド

組合せ数学では、 n次アステカダイヤモンドは、中心 ( x、y ) が | x | + | y | ≤ nを満たす正方格子のすべての正方形から構成されます。ここでn は固定された整数であり、正方格子は原点を頂点とする 4 つの単位正方形で構成され、xとy はどちらも半整数です。^[1]

アステカダイヤモンド定理によれば、 n次のアステカダイヤモンドのドミノタイルの数は2 ^{n ( n +1)/2}である。^[2]北極圏定理によれば、大きなアステカダイヤモンドのランダムなタイルは、特定の円の外側で固定される傾向がある。^[3]

タイルの色付けは、次の方法で行うのが一般的です。まず、ダイヤモンドの市松模様の色付けを考えてみましょう。各タイルは、正確に 1 つの黒い四角形を覆います。一番上の四角形が黒い四角形を覆う垂直タイルは 1 色で塗りつぶされ、他の垂直タイルは 2 色目で塗りつぶされます。水平タイルも同様です。

クヌースはまた、 n + 1/2次のアステカダイヤモンドを定義しました。 ^{[4]これらは、}中心平方数に関連付けられたポリオミノと同一です。

タイルを数えるのに非常に便利なのは、対応する有向グラフを通る交差しない経路を見ることです。タイル（ドミノタイル）を通る動きを次のように 定義すると、

• （１，１）垂直タイリングの一番下にいるとき
• （1,0）ここで水平方向のタイリングの終わりです
• (1,-1) 垂直タイリングの最上部にいるとき

すると、任意のタイリングを通じて、ソースからシンクへのパスが得られます。これらの動きは、シュレーダーパスに似ています。たとえば、次数 2 のアステカダイヤモンドを考えてみましょう。有向グラフを描画した後、ソースとシンクにラベルを付けることができます。はソースで、はシンクです。有向グラフ上で、からへのパスを描くことができ、パス行列、 、 が得られます。${\displaystyle a_{1},a_{2}}$${\displaystyle b_{1},b_{2}}$${\displaystyle a_{i}}$${\displaystyle b_{j}}$${\displaystyle P_{2}}$

${\displaystyle P_{2}={\begin{bmatrix}a_{1}b_{1}&a_{2}b_{1}\\a_{1}b_{2}&a_{2}b_{2}\\\end{bmatrix}}={\begin{bmatrix}6&2\\2&2\\\end{bmatrix}}}$

ここで、からへのすべての経路。順序2のタイリングの数は ${\displaystyle a_{i}b_{j}=}$${\displaystyle a_{i}}$${\displaystyle b_{j}}$

詳細${\displaystyle (P_{2})=12-4=8=2^{2(2+1)/2}}$

リンドストローム・ゲッセル・ヴィエノによれば、有向グラフの すべてのソースの集合をS 、すべてのシンクの集合をTとすると、

SからTまでの交差しない経路の数を求める^。[5]${\displaystyle (P_{n})=}$

アステカダイヤモンドの有向グラフを考えると、シュレーダーパスとアステカダイヤモンドのタイリングは一対一であることもEuとFuによって示されています。^[6]したがって、パス行列の行列式を見つけることで、n次のアステカダイヤモンドのタイリングの数が得られます。 ${\displaystyle P_{n}}$

アステカダイヤモンドのタイルの数を決定する別の方法は、大シュレーダー数と小シュレーダー数のハンケル行列を使うことです。 ^[6]再びリンドストローム・ゲッセル・ヴィエノの方法を用います。 ^[5]これらの行列の行列式を求めると、タイルと一対一である小シュレーダー数と大シュレーダー数の交差しない経路の数が得られます。小シュレーダー数は で、大シュレーダー数は であり、一般に2つのハンケル行列は次のようになります。 ${\displaystyle \{1,1,3,11,45,\cdots \}=\{y_{0},y_{1},y_{2},y_{3},y_{4},\cdots \ }}$${\displaystyle \{1,2,6,22,90,\cdots \}=\{x_{0},x_{1},x_{2},x_{3},x_{4},\cdots \}}$

${\displaystyle H_{n}={\begin{bmatrix}x_{1}&x_{2}&\cdots &x_{n}\\x_{2}&x_{3}&\cdots &x_{n+1}\\\vdots &\vdots &&\vdots \\x_{n}&x_{n+1}&\cdots &x_{2n-1}\\\end{bmatrix}}}$ そして ${\displaystyle G_{n}={\begin{bmatrix}y_{1}&y_{2}&\cdots &y_{n}\\y_{2}&y_{3}&\cdots &y_{n+1}\\\vdots &\vdots &&\vdots \\y_{n}&y_{n+1}&\cdots &y_{2n-1}\\\end{bmatrix}}}$

ここで、detおよび detです (detであることも事実です。これは のようなハンケル行列ですが、左上隅の行列の最初のエントリとして ではなくで始まります)。${\displaystyle (H_{n})=2^{n(n+1)/2}}$${\displaystyle (G_{n})=2^{n(n-1)/2}}$${\displaystyle n\geq 1}$${\displaystyle (H_{n}^{0})=2^{n(n-1)/2}}$${\displaystyle H_{n}}$${\displaystyle x_{0}}$${\displaystyle x_{1}}$

ブロックの形を考えてみると、 n次アステカダイヤモンドの場合と同じ疑問が浮かび上がる。これは多くの論文で証明されているので、参照することとする。^[7]ブロックの形を とすると、 ${\displaystyle 2\times n}$${\displaystyle 2\times n}$${\displaystyle B_{n}}$

タイルの数は${\displaystyle B_{n}=F_{n}}$

ここで はn 番目のフィボナッチ数で、 です。 は 1 通りの方法でしかタイルを敷くことができず、 通りの方法がない図形であることがわかっています。帰納法を使って、 と、タイルを敷く方法しかないドミノタイルを考えます。 のタイルの敷き方の数を仮定すると、 を考えます。 タイルの敷き方を開始する方法に注目すると、2 つのケースがあります。最初のタイルを垂直にして開始すると、異なるタイルの敷き方を持つ が残ります。 タイルの敷き方を開始するもう 1 つの方法は、2 つの水平タイルを重ねることです。この場合、異なるタイルの敷き方を持つ が残ります。この 2 つを足すと、 のタイルの敷き方は です。^[7]${\displaystyle F_{n}}$${\displaystyle ^{th}}$ ${\displaystyle n\geq 0}$${\displaystyle B_{0}}$${\displaystyle 2\times 0}$${\displaystyle B_{1}}$${\displaystyle 2\times 1}$ ${\displaystyle F_{1}=1}$${\displaystyle B_{n}=F_{n}}$${\displaystyle B_{n+1}}$${\displaystyle B_{n}}$${\displaystyle F_{n}}$${\displaystyle B_{n-1}}$${\displaystyle F_{n-1}}$${\displaystyle B_{n+1}=F_{n}+F_{n-1}=F_{n+1}}$

アステカ ダイヤモンドの有効なタイリングを見つけるには、基礎となる集合被覆問題の解決が必要です。を 2X1 ドミノの集合とします。この集合では、他のドミノが存在しない場合に、D 内の各ドミノをダイヤモンド内に (境界を越えずに) 配置できます。 を、ダイヤモンド内にある、被覆する必要がある 1X1 の正方形の集合とします。D 内の 2 つのドミノは、S 内の任意の境界正方形を被覆できます。また、D 内の 4 つのドミノは、S 内の任意の境界以外の正方形を被覆できます。 ${\displaystyle D=\{d_{1},d_{2},\dots ,d_{n}\}}$${\displaystyle S=\{s_{1},s_{2},\dots ,s_{m}\}}$

を正方形 を覆うドミノの集合と定義し、を、ドミノがタイリングに使用される場合は、そうでない場合は 0となる指示変数とします。これらの定義により、アステカのダイヤモンドをタイリングするタスクは、2 進整数計画として定式化された制約充足問題に簡略化できます。 ${\displaystyle c(s_{i})\subset D}$${\displaystyle s_{i}}$${\displaystyle x_{i}}$${\displaystyle x_{i}=1}$${\displaystyle i^{th}}$

${\displaystyle \min \sum _{1\leq i\leq m}0\cdot x_{i}}$

以下が適用されます: 、 および。 ${\displaystyle \sum _{i\in c(s_{i})}x_{i}=1,}$${\displaystyle 1\leq i\leq m}$${\displaystyle x_{i}\in \{0,1\}}$

制約は、正方形が1 つのタイルで覆われることを保証し、制約のコレクションは、各正方形が覆われること (覆いに穴がない) を保証します。この定式化は、標準の整数プログラミング パッケージを使用して解決できます。追加の制約を構築して、特定のドミノの配置を強制したり、水平または垂直方向のドミノの最小数が使用されるようにしたり、個別のタイリングを生成したりできます。 ${\displaystyle i^{th}}$${\displaystyle s_{i}}$${\displaystyle m}$

別のアプローチとしては、Knuth のアルゴリズム X を適用して、問題の有効なタイリングを列挙することです。

• ワイスタイン、エリック・W.「アステカ・ダイヤモンド」。マスワールド。