A bijection proving the Aztec diamond theorem by combing lattice paths

MaRDI QIDQ396947zbMATH OpenFDO

Authors Frédéric Bosio, Marc van Leeuwen

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.5373, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p24

zbMATH Keywords

domino tilingbijective proofalgorithmic bijectionAztec diamondnon-intersecting paths

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19)

Abstract: We give a bijective proof of the Aztec diamond theorem, stating that there are $2^{n(n+1)/2}$ domino tilings of the Aztec diamond of order $n$. The proof in fact establishes a similar result for non-intersecting families of $n+1$ Schr"oder paths, with horizontal, diagonal or vertical steps, linking the grid points of two adjacent sides of an $nimesn$ square grid; these families are well known to be in bijection with tilings of the Aztec diamond. Our bijection is produced by an invertible "combing" algorithm, operating on families of paths without non-intersection condition, but instead with the requirement that any vertical steps come at the end of a path, and which are clearly $2^{n(n+1)/2}$ in number; it transforms them into non-intersecting families.

Recommendations

• A new simple proof of the Aztec diamond theorem
• A simple proof of the Aztec diamond theorem
• Two new bijections on lattice paths
• A generalization of Aztec diamond theorem. I
• Lattice path encodings in a combinatorial proof of a differential identity
• Bijections between lattice paths and plane partitions
• A combinatorial proof of a recursive relation of the Motzkin sequence by lattice paths
• A visual proof of a result of Knuth on spanning trees of Aztec diamonds in the case of odd order
• A bijection on Dyck paths and its consequences
• A simple proof for the number of tilings of quartered Aztec diamonds

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• A simple proof of the Aztec diamond theorem
• Alternating-sign matrices and domino tilings. I
• Aztec diamonds and digraphs, and Hankel determinants of Schröder numbers
• Markov chain algorithms for planar lattice structures
• Non-intersecting paths, random tilings and random matrices
• Perfect matchings of cellular graphs
• Remark on the dimer problem

Cited in

(17)

• Enumeration of antisymmetric monotone triangles and domino tilings of quartered Aztec rectangles
• Generating function of the tilings of an Aztec rectangle with holes
• Multiply-refined enumeration of alternating sign matrices
• A generalization of Aztec diamond theorem. I
• An extension of the Lindström-Gessel-Viennot theorem
• A generalization of Aztec diamond theorem. II.
• A simple proof of the Aztec diamond theorem
• Linear recurrences for cylindrical networks
• Off-diagonally symmetric domino tilings of the Aztec diamond of odd order
• Domino tilings for augmented Aztec rectangles and their chains
• Laurent biorthogonal polynomials, \( q\)-Narayana polynomials and domino tilings of the Aztec diamonds
• A new simple proof of the Aztec diamond theorem
• Domino tilings and Aztec stars
• Domino tilings with barriers
• Proof without words: independent sets in grid graphs and tilings of Aztec diamonds
• Domino tilings of Aztec octagons
• Off-diagonally symmetric domino tilings of the Aztec diamond

This page was built for publication: A bijection proving the Aztec diamond theorem by combing lattice paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396947)