<> Definition & Example ==================== - A **perfect matching** of the set $\{1,2,3,\ldots,2n\}$ is a [partition](/SetPartitions) into blocks of size 2. <> - There are $(2n-1)!! = 1 \cdot 3 \cdot 5 \cdot \cdots \cdot (2n - 1)$ such perfect matchings, see [OEIS:A001147](https://oeis.org/A001147). Additional information ====================== - Perfect matchings can also be seen as fixed point free involutions on $\mathcal{S}$. - Perfect matchings have a matrix known as the Weingarten matrix which are used to compute polynomial integrals over the orthogonal group $O_N$ <>. - Perfect matchings correspond to Kekulé structures in chemistry and give important information about the chemical structure of compounds. Applications include estimation of resonance energy, estimation of π-electron energy, and estimation of bond lengths. - [Hall's marriage theorem](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem) provides a characterization of bipartite graphs which have a perfect matching. - [Tutte's theorem](https://en.wikipedia.org/wiki/Tutte_theorem) provides a characterization for arbitrary graphs which have a perfect matching. References ========== - [Sage reference manual](http://www.sagemath.org/doc/reference/sage/combinat/perfect_matching.html) - [Wolfram MathWorld](http://mathworld.wolfram.com/PerfectMatching.html) <> Sage examples ============= {{{#!sagecell for n in [1,2,3,4]: P = PerfectMatchings(2*n) print n, P.cardinality() for pm in PerfectMatchings(4): print pm, pm.number_of_crossings(), pm.number_of_nestings(), pm.to_permutation() }}} Technical information for database usage ======================================== - A perfect matching is uniquely represented as a sorted list of increasing pairs. - Perfect matchings are graded by the size. - The database contains all perfect matchings of size at most 10.