
In combinatorial mathematics, an Aztec diamond of order n consists of all squares of a square lattice whose centers (x,y) satisfy |x| + |y| ≤ n. Here n is a fixed integer, and the square lattice consists of unit squares with the origin as a vertex of 4 of them, so that both x and y are half-integers.
The Aztec diamond theorem states that the number of domino tilings of the Aztec diamond of order n is 2n(n+1)/2. The Arctic Circle theorem says that a random tiling of a large Aztec diamond tends to be frozen outside a certain circle.
It is common to color the tiles in the following fashion. First consider a checkerboard coloringof the diamond. Each tile will cover exactly one black square. Vertical tiles where the top square covers a black square,is colored in one color, and the other vertical tiles in a second. Similarly for horizontal tiles.
Knuth has also defined Aztec diamonds of order n + 1/2. They are identical with the polyominoes associated with the centered square numbers.
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
| y=k+ | 1 |
| 2 |
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
aa,a2
b1,b2
ai
bj
(i,j)\in\{1,2\} x \{1,2\}
Ci,j
P2= \begin{bmatrix} C1,1&C1,2\\ C2,1&C2,2\\ \end{bmatrix}=\begin{bmatrix} 6&2\\ 2&2\\ \end{bmatrix}.
Then by the Lindström-Gessel-Viennot lemma, the number of non-intersecting paths for order 2 is
det
(P2)=12-4=8=22(2+1)/2,
the same as the number of domino tilings. More generally,det
(Pn)=
It has been shown by Eu and Fu that Schröder paths and the tilings of the Aztec diamond are in bijection. Hence, finding the determinant of the path matrix
Pn
Another way to determine the number of tilings of an Aztec diamond is using Hankel matrices of large and small Schröder numbers, using the method from Lindstrom-Gessel-Viennot again. 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
\{1,1,3,11,45, … \}=\{y0,y1,y2,y3,y4, … \}
\{1,2,6,22,90, … \}=\{x0,x1,x2,x3,x4, … \}
Hn=\begin{bmatrix} x1&x2& … &xn\\ x2&x3& … &xn+1\\ \vdots&\vdots&&\vdots\\ xn&xn+1& … &x2n-1\\ \end{bmatrix}
Gn=\begin{bmatrix} y1&y2& … &yn\\ y2&y3& … &yn+1\\ \vdots&\vdots&&\vdots\\ yn&yn+1& … &y2n-1\\ \end{bmatrix}
where det
(Hn)=2n(n+1)/2
(Gn)=2n(n-1)/2
n\geq1
| 0) | |
| (H | |
| n |
=2n(n-1)/2
Hn
x0
x1
Finding valid tilings of the Aztec diamond involves the solution of the underlying set-covering problem. Let
D=\{d1,d2,...,dn\}
S=\{s1,s2,...,sm\}
Define
c(si)\subD
si
xi
xi=1
ith
min\sum1\leq0 ⋅ xi
Subject to:
| \sum | |
| i\inc(si) |
xi=1,
1\leqi\leqm
xi\in\{0,1\}
The
ith
si
m
An alternative approach is to apply Knuth's Algorithm X to enumerate valid tilings for the problem.