Solution
The Aztec Diamond
Show the problem again
The Aztec diamond of order 4 is the region of the square grid made of 8 rows of unit squares whose lengths are 2, 4, 6, 8, 8, 6, 4, 2, with every row centred on the same vertical axis (equivalently, the union of all unit grid squares whose centres satisfy |x| + |y| ≤ 4). It contains 40 squares. In how many ways can this region be tiled exactly by 20 dominoes (1 × 2 rectangles placed horizontally or vertically)? Give an integer.
Worked solution
**Answer: 1024.** Let AD(n) be the number of domino tilings of the Aztec diamond of order n. Small cases: order 1 is a 2 × 2 square with 2 tilings, and order 2 (rows 2, 4, 4, 2) has 8. The theorem of Elkies, Kuperberg, Larsen and Propp is that AD(n) = 2^(n(n+1)/2). One slick proof uses Kuo's graphical condensation, which yields AD(n) · AD(n − 2) = 2 · AD(n − 1)^2. From AD(0) = 1 and AD(1) = 2 this gives AD(2) = 8, AD(3) = 2 · 64 / 2 = 64, and AD(4) = 2 · 64² / 8 = 1024. Another proof, "domino shuffling", builds every tiling of order n from one of order n − 1 together with n free binary choices, which is exactly the factor 2^n in AD(n) = 2^n · AD(n − 1). So the order-4 diamond has 2^10 = 1024 tilings (confirmed by exhaustive search).
Source: Aztec diamonds and their tiling count are due to N. Elkies, G. Kuperberg, M. Larsen and J. Propp (1992). Statement written for AxiomIQ.