Enumeration of Matchings — Problem 9

Definitions and mathematical statement

A domino is the union of two unit lattice squares sharing an edge. A domino tiling of a finite region of unit squares is a partition of its squares into dominoes. The source discusses Aztec rectangles whose dimensions differ by one, with the larger dimension odd, and deletion of the central square to restore equality between the numbers of black and white squares in a checkerboard coloring. This equality is a necessary condition for tileability.

The source does not explicitly define its Aztec-rectangle convention. A concrete coordinate interpretation consistent with its supplied illustration is the following. For a positive integer $n$, let \[ S_n=\left\{(i,j)\in{\mathbb{Z}}^2: |i+j|\leq 2n,\quad |i-j|\leq 2n+1\right\}, \] and associate to $(i,j)$ the unit square \[ Q_{i,j}=[i-\tfrac12,i+\tfrac12]\times[j-\tfrac12,j+\tfrac12]. \] The central square is $Q_{0,0}$. Define the region after deletion by \[ R_n=\bigcup_{(i,j)\in S_n\setminus\{(0,0)\}}Q_{i,j}. \] Equivalently, let $V_n=S_n\setminus\{(0,0)\}$, and let \[ E_n=\left\{\{(i,j),(k,\ell)\}\subseteq V_n: |i-k|+|j-\ell|=1\right\}. \] A perfect matching is a subset $M\subseteq E_n$ in which every vertex of $V_n$ belongs to exactly one edge. Such matchings correspond to domino tilings of $R_n$. Write \[ T(n)=\#\left\{M\subseteq E_n:M\text{ is a perfect matching of }(V_n,E_n)\right\}. \] Enumeration problem (Propp, 1998, Problem 9). Find a formula, valid for every positive integer $n$, for the number of domino tilings of the $2n$-by-$(2n+1)$ Aztec rectangle with its central square removed; under the coordinate interpretation above, this is $T(n)$.

Unresolved qualifications. The coordinate realization is an explicit interpretation of the source terminology and illustration, rather than a definition quoted from the supplied record. Its identification with the intended Aztec rectangle requires review. The source also leaves the range of $n$ unstated; positive integers are used here as the intended nondegenerate range.

Short English statement

Propp asks for a formula counting domino tilings of a $2n$-by-$(2n+1)$ Aztec rectangle after deleting its central square. The draft gives a precise candidate lattice model, whose agreement with the source's geometric convention requires review. The supplied registry labels the problem open; that status has not been independently verified.

Sources

• UnsolvedMath local source registry, permanent ID $800338$, exact source problem code catalogue entry, title "Enumeration of Matchings --- Problem 9." The supplied record attributes the problem to Propp, with proposed year 1998, and labels it open.
• Propp, Twenty Open Problems in Enumeration of Matchings (1998), Problem 9 (#9). Supplied source URL: https://arxiv.org/abs/math/9801060. The background records access on 2026-10-16 and extraction method arxiv_latex. These are supplied provenance statements, not a claim of independent source access or verification.
• Supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82. The supplied record was created and updated on 2026-10-16. Its open-status label is supplied curation, not an independently verified literature assessment.