{{short description|Shape in mathematics of domino tiling}} thumb|An Aztec diamond of order 4
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.<ref>{{Citation | author-link=Richard P. Stanley | last1=Stanley | first1=Richard P. | title=Enumerative combinatorics. Vol. 2 | url=http://www-math.mit.edu/~rstan/ec/ | publisher=Cambridge University Press | series=Cambridge Studies in Advanced Mathematics | isbn=978-0-521-56069-6 | mr=1676282 | year=1999 | volume=62 | access-date=2008-11-18 | archive-url=https://web.archive.org/web/20081005112920/http://www-math.mit.edu/~rstan/ec/# | archive-date=2008-10-05 | url-status=live }}</ref>
thumb|One of 1024 possible domino tilings of an order 4 Aztec diamond thumb|A domino tiling of an order-50 Aztec diamond, chosen uniformly at random. The four corners of the diamond outside of the roughly circular area are "frozen". The '''Aztec diamond theorem''' states that the number of domino tilings of the Aztec diamond of order ''n'' is 2<sup>''n''(''n''+1)/2</sup>.<ref>{{Citation | last1=Elkies | first1=Noam | author1-link = Noam Elkies | last2=Kuperberg | first2=Greg | author2-link = Greg Kuperberg | last3=Larsen | first3=Michael | author3-link = Michael J. Larsen | last4=Propp | first4=James | author4-link = Jim Propp | title=Alternating-sign matrices and domino tilings. I | doi=10.1023/A:1022420103267 | mr=1226347 | year=1992 | journal=Journal of Algebraic Combinatorics | issn=0925-9899 | volume=1 | issue=2 | pages=111–132| doi-access=free }}</ref> The '''Arctic Circle theorem''' says that a random tiling of a large Aztec diamond tends to be frozen outside a certain circle.<ref>{{Citation | last1=Jockusch | first1=William | last2=Propp | first2=James | last3=Shor | first3=Peter | title=Random Domino Tilings and the Arctic Circle Theorem | arxiv=math/9801068 | year=1998| bibcode=1998math......1068J }}</ref>
It is common to color the tiles in the following fashion. First consider a checkerboard coloring of 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.<ref>{{Citation | last1=Knuth | first1=Donald E. | author1-link=Donald Knuth | title=The Art of Computer Programming | volume=4 | section=Pre-Fascicle 5c (section 7.2.2.1, Dancing Links) | page=93 | year=2019 | url=https://www-cs-faculty.stanford.edu/~knuth/fasc5c.ps.gz}}</ref> They are identical with the polyominoes associated with the centered square numbers.
== Non-intersecting paths == 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 <math>y=k+\frac{1}{2}</math> 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 <math>a_a,a_2</math> and its sinks <math>b_1,b_2</math>. On its directed graph, we can count the directed paths from <math>a_i</math> to <math>b_j</math> for each pair <math>(i,j) \in \{1,2\} \times \{1,2\}</math>. Call <math>C_{i,j}</math> the result of each counting. This gives us a matrix,
<math> 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}. </math>
Then by the Lindström-Gessel-Viennot lemma<ref name = "Gessel"/>, the number of non-intersecting paths for order 2 is
det<math>(P_2) = 12 - 4 = 8 = 2^{2(2+1)/2},</math>
the same as the number of domino tilings. More generally, det<math>(P_n) =</math> 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.<ref name = "Eu"/> Hence, finding the determinant of the path matrix <math>P_n</math> 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,<ref name = "Eu"/> using the method from Lindstrom-Gessel-Viennot again.<ref name = "Gessel"/> 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 <math> \{1,1,3,11,45,\cdots\} = \{y_0, y_1,y_2,y_3,y_4,\cdots\}</math> and the large Schröder numbers are <math> \{1,2,6,22,90,\cdots\}=\{x_0,x_1,x_2,x_3,x_4,\cdots\} </math>, and in general our two Hankel matrices will be
<math> 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} </math> and <math> 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} </math>
where det<math>(H_n) = 2^{n(n+1)/2}</math> and det<math>(G_n) = 2^{n(n-1)/2}</math> where <math>n \geq 1</math> (It also true that det<math>(H_n^0) = 2^{n(n-1)/2}</math> where this is the Hankel matrix like <math>H_n</math>, but started with <math>x_0</math> instead of <math>x_1</math> for the first entry of the matrix in the top left corner).
==Generating valid tilings== Finding valid tilings of the Aztec diamond involves the solution of the underlying set-covering problem. Let <math>D=\{d_1,d_2,\dots,d_n\}</math> 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 <math>S = \{s_1,s_2,\dots,s_m\}</math> 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 <math> c(s_i)\sub D</math> to be the set of dominoes that cover square <math>s_i</math>, and let <math>x_i</math> be an indicator variable such that <math>x_i =1</math> if the <math>i^{th}</math> 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:
<math> \min \sum_{1\leq i\leq m} 0\cdot x_i </math>
Subject to: <math> \sum_{i\in c(s_i)} x_i = 1, </math> for <math>1\leq i \leq m </math>, and <math> x_i \in \{0,1\}</math>.
The <math>i^{th}</math> constraint guarantee that square <math>s_i</math> will be covered by a single tile, and the collection of <math>m</math> 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.
==References== <references>
<ref name="Eu">{{cite journal|last1=Eu|first1=Sen-Peng|last2=Fu|first2=Tung-Shan|title=A Simple Proof of the Aztec Diamond|journal=Electron. J. Combin., 12:Research Paper|year=2005|page=0412041|publisher=The Electroninc Journal of Combinatorics|citeseerx=10.1.1.214.7065}}</ref> <ref name="Gessel">{{cite web|last1=Majumdar|first1=Diptapriyo|title=Advance Graph Algorithms: Lemma of Gessel Viennot|url=https://www.imsc.res.in/~ashutosh/lectures/Presentation_Diptapriyo.pdf|accessdate=22 April 2014|archive-url=https://web.archive.org/web/20180305142732/https://www.imsc.res.in/~ashutosh/lectures/Presentation_Diptapriyo.pdf#|archive-date=2018-03-05|url-status=live}}</ref>
</references>
==External links== * {{mathworld|title=Aztec Diamond|urlname=AztecDiamond}}
Category:Enumerative combinatorics