A bijection proving the Aztec diamond theorem by combing lattice paths (Q396947)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A bijection proving the Aztec diamond theorem by combing lattice paths |
scientific article |
Statements
A bijection proving the Aztec diamond theorem by combing lattice paths (English)
0 references
14 August 2014
0 references
Summary: 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öder paths, with horizontal, diagonal or vertical steps, linking the grid points of two adjacent sides of an \(n\times n\) 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.
0 references
Aztec diamond
0 references
domino tiling
0 references
non-intersecting paths
0 references
bijective proof
0 references
algorithmic bijection
0 references