A bijection proving the Aztec diamond theorem by combing lattice paths (Q396947)

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.