Enumeration of Matchings — Problem 14

Definitions and mathematical statement

The supplied record does not define an Aztec window. The following statement therefore uses an explicit, conditional interpretation: a concentric difference of two Aztec diamonds on the same square lattice. This geometric convention and the parameter range require confirmation against the cited source.

For an integer $n\geq 0$, define the collection of cells of the order-$n$ Aztec diamond by \[ \mathcal D_n=\left\{[i,i+1]\times[j,j+1]:i,j\in{\mathbb{Z}},\ \left|i+\tfrac12\right|+\left|j+\tfrac12\right|\leq n\right\}. \] For positive integers $x,w$, define the window with inner order $x$ and outer order $x+w$ by the difference of cell collections \[ \mathcal W_{x,w}=\mathcal D_{x+w}\setminus\mathcal D_x. \] A domino tiling is a partition of these cells into pairs sharing a full side. Write $T(x,w)$ for the number of such partitions.

Problem (Propp, 1998, Problem 14; conditional geometric interpretation). Find a general formula for $T(x,w)$. The source also identifies the following weaker objective as progress: explain why, for every fixed positive integer $w$, there is a polynomial $P_w\in{\mathbb{Q}}[X]$ such that \[ T(x,w)=P_w(x)\qquad\text{for every positive integer }x. \] This is a requested polynomiality statement, not an established assertion. The supplied excerpt does not specify whether inner order zero is included, or explicitly settle the geometric conventions used above.

Short English statement

Count domino tilings of Aztec windows with inner order $x$ and outer order $x+w$. Even proving polynomial dependence on $x$ for each fixed width $w$ is a stated objective. The explicit concentric lattice definition above is conditional and requires source confirmation.

Sources

• Local UnsolvedMath registry: supplied complete source record with permanent ID $800343$, source problem code catalogue entry, title Enumeration of Matchings --- Problem 14. The record attributes the problem to Propp, with proposed year 1998.
• Propp, Twenty Open Problems in Enumeration of Matchings (1998), Problem 14 (#14). Supplied source URL: https://arxiv.org/abs/math/9801060.
• Supplied provenance records access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance claims; no independent source access or verification is asserted here.
• The registry labels the problem open. This is a supplied status label, not an independently verified assessment of the literature.