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. If we define our movements through a tiling (domino tiling) to be
Then through any tiling we can have these paths from our sources to our sinks. 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 and sinks.
a1,a2
b1,b2
ai
bj
P2
P2= \begin{bmatrix} a1b1&a2b1\\ a1b2&a2b2\\ \end{bmatrix}=\begin{bmatrix} 6&2\\ 2&2\\ \end{bmatrix}
where
aibj=
ai
bj
det
(P2)=12-4=8=22(2+1)/2
According to Lindstrom-Gessel-Viennot, if we let S be the set of all our sources and T be the set of all our sinks of our directed graph then
det
(Pn)=
Considering the directed graph of the Aztec Diamond, it has also 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
Consider the shape,
2 x n
2 x n
Bn
The number of tilings of
Bn=Fn
where
Fn
th
n\geq0
B0
2 x 0
B1
2 x 1
F1=1
Bn=Fn
Bn+1
Bn
Fn
Bn-1
Fn-1
Bn+1=Fn+Fn-1=Fn+1
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.