Enumeration of Matchings — Problem 13

Definitions and mathematical statement

For a finite square-grid region encoded by a finite set $R\subseteq{\mathbb{Z}}^2$ of unit cells, a domino tiling is a partition of $R$ into two-element sets $\{(i,j),(k,\ell)\}$ satisfying $|i-k|+|j-\ell|=1$. Define \[ T(R)=\#\left\{\mathcal D:\mathcal D\text{ is a domino tiling of }R\right\}. \] The supplied problem asks for a general formula for the number of domino tilings of even pillows. If these objects are finite square-grid regions, and $\mathcal E$ denotes their intended family, the requested enumeration is a formula for $T(R)$ for every $R\in\mathcal E$.

This is only a conditional formulation: the supplied record does not define a pillow, its boundary, its size parameters, or the meaning of even. Consequently, it does not specify $\mathcal E$, and the intended enumeration problem cannot be stated completely from the supplied material.

Short English statement

Propp's Problem 13 asks for a general formula counting domino tilings of even pillows. The supplied record omits the definition of these regions and the meaning of even, so the family to be counted remains unspecified.

Sources

• Local UnsolvedMath registry, supplied complete record: permanent ID $800342$, exact source problem code catalogue entry, title "Enumeration of Matchings — Problem 13." The record attributes the problem to Propp, with proposed year 1998.
• Propp, Twenty Open Problems in Enumeration of Matchings (1998), Problem 13 (#13). Supplied source URL: https://arxiv.org/abs/math/9801060. The supplied provenance records access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance claims, not independently verified access or extraction.
• The local record labels the problem open. This is a supplied registry classification, not an independently verified assessment of the mathematical literature.