Aztec diamond

Aztec diamond (Redirected from Aztec diamond theorem) Jump to navigation Jump to search 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.[1] One of 1024 possible domino tilings of an order 4 Aztec diamond 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 2n(n+1)/2.[2] The Arctic Circle theorem says that a random tiling of a large Aztec diamond tends to be frozen outside a certain circle.[3] 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.[4] They are identical with the polyominoes associated with the centered square numbers.

Conteúdo 1 Non-intersecting paths 2 Other tiling problems 3 Generating valid tilings 4 Referências 5 External links Non-intersecting paths 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 (1,1) when we are the bottom of a vertical tiling (1,0) where we are the end of a horizontal tiling (1,-1) when we are at the top of a vertical tiling Then through any tiling we can have these paths from our sources to our sinks. These movements are similar to Schröder paths. Por exemplo, consider an Aztec Diamond of order 2, and after drawing its directed graph we can label its sources and sinks. {estilo de exibição a_{1},uma_{2}} are our sources and {estilo de exibição b_{1},b_{2}} are our sinks. On its directed graph, we can draw a path from {estilo de exibição a_{eu}} para {estilo de exibição b_{j}} , this gives us a path matrix, {estilo de exibição P_{2}} , {estilo de exibição P_{2}={começar{bmatriz}uma_{1}b_{1}&a_{2}b_{1}\uma_{1}b_{2}&a_{2}b_{2}\fim{bmatriz}}={começar{bmatriz}6&2\2&2\end{bmatriz}}} Onde {estilo de exibição a_{eu}b_{j}=} all the paths from {estilo de exibição a_{eu}} para {estilo de exibição b_{j}} . The number of tilings for order 2 is det {estilo de exibição (P_{2})=12-4=8=2^{2(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 {estilo de exibição (P_{n})=} number of non-intersecting paths from S to T.[5] 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.[6] Por isso, finding the determinant of the path matrix, {estilo de exibição 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 {estilo de exibição {1,1,3,11,45,cdots }={s_{0},s_{1},s_{2},s_{3},s_{4},cdots }} and the large Schröder numbers are {estilo de exibição {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 {estilo de exibição H_{n}={começar{bmatriz}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}\fim{bmatriz}}} e {estilo de exibição G_{n}={começar{bmatriz}s_{1}&y_{2}&cdots &y_{n}\s_{2}&y_{3}&cdots &y_{n+1}\vdots &vdots &&vdots \y_{n}&y_{n+1}&cdots &y_{2n-1}\fim{bmatriz}}} where det {estilo de exibição (H_{n})=2^{2(n+1)/2}} and det {estilo de exibição (G_{n})=2^{2(n-1)/2}} Onde {ngeq de estilo de exibição 1} (It also true that det {estilo de exibição (H_{n}^{0})=2^{2(n-1)/2}} where this is the Hankel matrix like {estilo de exibição H_{n}} , but started with {estilo de exibição x_{0}} ao invés de {estilo de exibição x_{1}} for the first entry of the matrix in the top left corner).

Other tiling problems Consider the shape, {displaystyle 2times n} bloquear, and we can ask the same question as for the Aztec Diamond of order n. As this has been proven in many papers, we will refer to.[7] Letting the {displaystyle 2times n} block shape be denoted by {estilo de exibição B_{n}} , then it can be seen The number of tilings of {estilo de exibição B_{n}=F_{n}} Onde {estilo de exibição F_{n}} is the n {displaystyle ^{º}} Fibonacci number and {ngeq de estilo de exibição 0} . It is understood that {estilo de exibição B_{0}} é um {displaystyle 2times 0} shape that can only be tiled 1 caminho, no ways. Using induction, considerar {estilo de exibição B_{1}} and that is just {displaystyle 2times 1} domino tile where there is only {estilo de exibição F_{1}=1} tiling. Assuming the number of tilings for {estilo de exibição B_{n}=F_{n}} , then we consider {estilo de exibição B_{n+1}} . Focusing on how we can begin our tiling, we have two cases. We can start with our first tile being vertical, which means we are left with {estilo de exibição B_{n}} que tem {estilo de exibição F_{n}} different tilings. The other way we can start our tiling is by laying two horizontal tiles on top of each other, which leaves us with {estilo de exibição B_{n-1}} that has {estilo de exibição F_{n-1}} different tilings. By adding the two together, the number of tilings for {estilo de exibição B_{n+1}=F_{n}+F_{n-1}=F_{n+1}} .[7] Generating valid tilings Finding valid tilings of the Aztec diamond involves the solution of the underlying set-covering problem. Deixar {displaystyle D={d_{1},d_{2},pontos ,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. Deixar {estilo de exibição S={s_{1},s_{2},pontos ,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.

Definir {estilo de exibição c(s_{eu})subset D} to be the set of dominoes that cover square {estilo de exibição s_{eu}} , e deixar {estilo de exibição x_{eu}} be an indicator variable such that {estilo de exibição x_{eu}=1} if the {displaystyle i^{º}} domino is used in the tiling, e 0 por outro lado. 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 _{1leq ileq m}0cdot x_{eu}} Subject to: {soma de estilo de exibição _{iin c(s_{eu})}x_{eu}=1,} por {displaystyle 1leq ileq m} , e {estilo de exibição x_{eu}dentro {0,1}} .

o {displaystyle i^{º}} constraint guarantee that square {estilo de exibição s_{eu}} will be covered by a single tile, and the collection of {estilo de exibição 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.

References ^ Stanley, Ricardo P. (1999), Enumerative combinatorics. Volume. 2, Estudos de Cambridge em Matemática Avançada, volume. 62, Cambridge University Press, ISBN 978-0-521-56069-6, SENHOR 1676282, arquivado a partir do original em 2008-10-05, recuperado 2008-11-18 ^ Elkies, Noam; Kuperberg, Greg; Larsen, Michael; Propp, James (1992), "Alternating-sign matrices and domino tilings. EU", Journal of Algebraic Combinatorics, 1 (2): 111–132, doi:10.1023/UMA:1022420103267, ISSN 0925-9899, SENHOR 1226347 ^ Jockusch, William; Propp, James; Shor, Peter (1998), Random Domino Tilings and the Arctic Circle Theorem, arXiv:math/9801068, Bibcode:1998math......1068J ^ Knuth, Donald E. (2019), "Pre-Fascicle 5c (seção 7.2.2.1, Dancing Links)", The Art of Computer Programming, volume. 4, p. 93 ^ Saltar para: a b Majumdar, Diptapriyo. "Advance Graph Algorithms: Lemma of Gessel Viennot" (PDF). Arquivado (PDF) do original em 2018-03-05. Recuperado 22 abril 2014. ^ Saltar para: a b Eu, Sen-Peng; Fu, Tung-Shan (2005). "A Simple Proof of the Aztec Diamond". Electron. J. Combin., 12:Research Paper. The Electroninc Journal of Combinatorics: 0412041. CiteSeerX 10.1.1.214.7065. ^ Saltar para: a b Martinez, Megan; Kanoff, Ilene. "Domino Tiling and the Fibonacci numbers" (PDF). Arquivado (PDF) do original em 2016-05-03. Recuperado 2 Marchar 2018. Weissstein esquerdo externo, Eric W. "Aztec Diamond". MathWorld. Categorias: Enumerative combinatorics