Aztec diamond

Something that is very useful for counting tilings is looking at the non-intersecting paths through its corresponding directed graph. We define the graph's vertices to lie on the left and right edges of the squares, centered vertically (so ${\displaystyle y=k+{\frac {1}{2}}}$ for an integer k). The graph's directed edges are defined by the 3 vectors (1,1), (1,0) and (1,-1): For each vertex, if addition of a vector leads to another vertex and the connecting line segment lies within the Aztec diamond, there is a corresponding directed edge. Define the sources to be the vertices of negative y coordinate on the left edges of the Aztec diamond, and the sinks to be the vertices of negative y coordinate on the right edges of the Aztec diamond. Then a tiling defines a tuple of non-intersection paths by starting at each source and repeatedly applying the following rules:

• choose (1,1) at the bottom left vertex of a vertical tile,
• choose twice (1,0) at the left vertex of a horizontal tile,
• choose (1,-1) at a top left vertex of a vertical tile.

These movements are similar to Schröder paths. For example, consider an Aztec diamond of order 2, and after drawing its directed graph we can label its sources ${\displaystyle a_{a},a_{2}}$ and its sinks ${\displaystyle b_{1},b_{2}}$. On its directed graph, we can count the directed paths from ${\displaystyle a_{i}}$ to ${\displaystyle b_{j}}$ for each pair ${\displaystyle (i,j)\in \{1,2\}\times \{1,2\}}$. Call ${\displaystyle C_{i,j}}$ the result of each counting. This gives us a matrix,

${\displaystyle P_{2}={\begin{bmatrix}C_{1,1}&C_{1,2}\\C_{2,1}&C_{2,2}\\\end{bmatrix}}={\begin{bmatrix}6&2\\2&2\\\end{bmatrix}}.}$

Then by the Lindström-Gessel-Viennot lemma^[5], the number of non-intersecting paths for order 2 is

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

the same as the number of domino tilings. More generally, det${\displaystyle (P_{n})=}$ number of non-intersecting paths from sources to sinks.

It has been shown by Eu and Fu that Schröder paths and the tilings of the Aztec diamond are in bijection.^[6] Hence, finding the determinant of the path matrix ${\displaystyle P_{n}}$ will give us the number of tilings for the Aztec diamond of order n.

Another way to determine the number of tilings of an Aztec diamond is using Hankel matrices of large and small Schröder numbers,^[6] using the method from Lindstrom-Gessel-Viennot again.^[5] Finding the determinant of these matrices gives us the number of non-intersecting paths of small and large Schröder numbers, which is in bijection with the tilings. The small Schröder numbers are ${\displaystyle \{1,1,3,11,45,\cdots \}=\{y_{0},y_{1},y_{2},y_{3},y_{4},\cdots \}}$ and the large Schröder numbers are ${\displaystyle \{1,2,6,22,90,\cdots \}=\{x_{0},x_{1},x_{2},x_{3},x_{4},\cdots \}}$, and in general our two Hankel matrices will be

${\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}}}$ and ${\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}}}$

where det${\displaystyle (H_{n})=2^{n(n+1)/2}}$ and det${\displaystyle (G_{n})=2^{n(n-1)/2}}$ where ${\displaystyle n\geq 1}$ (It also true that det${\displaystyle (H_{n}^{0})=2^{n(n-1)/2}}$ where this is the Hankel matrix like ${\displaystyle H_{n}}$, but started with ${\displaystyle x_{0}}$ instead of ${\displaystyle x_{1}}$ for the first entry of the matrix in the top left corner).

Finding valid tilings of the Aztec diamond involves the solution of the underlying set-covering problem. Let ${\displaystyle D=\{d_{1},d_{2},\dots ,d_{n}\}}$ be the set of 2X1 dominoes where each domino in D may be placed within the diamond (without crossing its boundaries) when no other dominoes are present. Let ${\displaystyle S=\{s_{1},s_{2},\dots ,s_{m}\}}$ be the set of 1X1 squares lying within the diamond that must be covered. Two dominoes within D can be found to cover any boundary square within S, and four dominoes within D can be found to cover any non-boundary square within S.

Define ${\displaystyle c(s_{i})\subset D}$ to be the set of dominoes that cover square ${\displaystyle s_{i}}$, and let ${\displaystyle x_{i}}$ be an indicator variable such that ${\displaystyle x_{i}=1}$ if the ${\displaystyle i^{th}}$ domino is used in the tiling, and 0 otherwise. With these definitions, the task of tiling the Aztec diamond may be reduced to a constraint satisfaction problem formulated as a binary integer program:

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

Subject to: ${\displaystyle \sum _{i\in c(s_{i})}x_{i}=1,}$ for ${\displaystyle 1\leq i\leq m}$, and ${\displaystyle x_{i}\in \{0,1\}}$.

The ${\displaystyle i^{th}}$ constraint guarantee that square ${\displaystyle s_{i}}$ will be covered by a single tile, and the collection of ${\displaystyle m}$ constraints ensures that each square will be covered (no holes in the covering). This formulation can be solved with standard integer programming packages. Additional constraints can be constructed to force placement of particular dominoes, ensure a minimum number of horizontal or vertically-oriented dominoes are used, or generate distinct tilings.

An alternative approach is to apply Knuth's Algorithm X to enumerate valid tilings for the problem.