Enumeration of Matchings — Problem 2

Definitions and mathematical statement

A unit triangular lattice is a tiling of the plane by equilateral triangles of side length one. A lozenge is the union of two unit triangles sharing an edge. A lozenge tiling of a region is a finite collection of lozenges with pairwise disjoint interiors whose union is the region.

Under the usual lattice interpretation of the source, let $H_n$ be an equiangular hexagon with sides along lattice directions and cyclic side lengths \[ n,\ n+1,\ n,\ n+1,\ n,\ n+1. \] The natural parameter range is $n\in{\mathbb{Z}}_{\geq 1}$; this convention is explicit here because the supplied excerpt does not state the range or address degenerate cases.

Let $\Delta_n$ denote the triangular lattice region described in the source as the central triangle, and put \[ R_n=H_n\setminus\operatorname{int}(\Delta_n),\qquad a_n=\#\{\text{lozenge tilings of }R_n\}. \] The requested enumeration problem is to determine an explicit exact formula for $a_n$ for every admissible $n$.

Unresolved geometric qualification. The supplied excerpt does not explicitly give the side length or orientation of $\Delta_n$, or a construction identifying it uniquely. In particular, taking it to be a unit triangle would add a hypothesis not explicitly supplied. The counting problem above is therefore conditional on identifying the intended central triangular region; it does not yet specify a unique sequence of integers.

The introductory source prose compares preceding enumeration values with lozenge counts for the equal-sided $n,n,n,n,n,n$ hexagon. It reports an apparent linear-in-$n$ bound on their largest prime factors and suggests that an exact conjectural formula should be possible, with proof potentially harder. The preceding values and the antecedent of this observation are absent from the supplied record, so this observation is retained as source context rather than asserted as a mathematical bound.

Short English statement

Count the lozenge tilings of the lattice hexagon with alternating side lengths $n$ and $n+1$, after removing the intended central triangle, and seek an exact formula valid throughout the intended parameter range. The excerpt does not fully specify that triangle or the parameter range, so these require clarification before the draft defines a unique counting sequence. The registry labels the problem open; that label is supplied source metadata, not an independently verified literature assessment.

Sources

• Local UnsolvedMath registry, permanent ID $800331$, exact source problem code catalogue entry, title Enumeration of Matchings --- Problem 2; AMR Open Problem Lists collection. The record attributes the problem to Propp, with proposed year 1998, and supplies status open. Upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Propp, Twenty Open Problems in Enumeration of Matchings (1998), Problem 2 (#2), https://arxiv.org/abs/math/9801060. The supplied provenance reports access on 2026-10-16 and extraction by arxiv_latex. This access date and attribution are supplied provenance, not a claim of independent source consultation or verification.