Enumeration of Matchings — Problem 18

Definitions and mathematical statement

For a finite graph $G=(V,E)$, a perfect matching is a subset $M\subseteq E$ such that every vertex of $G$ is incident with exactly one edge of $M$. Define \[ \operatorname{pm}(G)=\left|\{M\subseteq E : M\text{ is a perfect matching of }G\}\right|. \] The supplied Problem 18 asks for $\operatorname{pm}(T_n)$, where $T_n$ denotes the source's "triangle graph of order $n$," for every order $n$ intended by that source.

The supplied record does not define $T_n$: its vertex set, edge set, boundary conventions, and admissible values of $n$ are unspecified. Thus this expresses the enumeration target only; a precise graph family and a fully determined mathematical problem require the missing definition. No particular triangular graph construction is selected here.

Short English statement

Count the perfect matchings of the triangle graph of each intended order $n$. The supplied record does not define that graph family or the allowed orders, so the enumeration problem remains underdetermined.

Sources

• Local UnsolvedMath registry, supplied record with permanent ID $800347$, source code catalogue entry, titled Enumeration of Matchings --- Problem 18. The record attributes the problem to Propp (1998) and labels it open; this is a supplied status, not an independently verified mathematical or literature assessment.
• Propp, Twenty Open Problems in Enumeration of Matchings (1998), Problem 18 (#18). Supplied source URL: https://arxiv.org/abs/math/9801060. The record reports access on 2026-10-16 and extraction by arxiv_latex; these provenance details are supplied and have not been independently verified.