Perfect matchings

A perfect matching of a set \(S\) is a partition into 2-element sets. If \(S\) is the set \(\{1,...,n\}\), it is equivalent to fixpoint-free involutions. These simple combinatorial objects appear in different domains such as combinatoric of orthogonal polynomials and of the hyperoctaedral groups (see [MV], [McD] and also [CM]):

AUTHOR:

  • Valentin Feray, 2010 : initial version
  • Martin Rubey, 2017: inherit from SetPartition, move crossings and nestings to SetPartition

EXAMPLES:

Create a perfect matching:

sage: m = PerfectMatching([('a','e'),('b','c'),('d','f')]);m
[('a', 'e'), ('b', 'c'), ('d', 'f')]

Count its crossings, if the ground set is totally ordered:

sage: n = PerfectMatching([3,8,1,7,6,5,4,2]); n
[(1, 3), (2, 8), (4, 7), (5, 6)]
sage: n.number_of_crossings()
1

List the perfect matchings of a given ground set:

sage: PerfectMatchings(4).list()
[[(1, 2), (3, 4)], [(1, 3), (2, 4)], [(1, 4), (2, 3)]]

REFERENCES:

[MV]combinatorics of orthogonal polynomials (A. de Medicis et X.Viennot, Moments des q-polynomes de Laguerre et la bijection de Foata-Zeilberger, Adv. Appl. Math., 15 (1994), 262-304)
[McD]combinatorics of hyperoctahedral group, double coset algebra and zonal polynomials (I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford University Press, second edition, 1995, chapter VII).
[CM]Benoit Collins, Sho Matsumoto, On some properties of orthogonal Weingarten functions, Arxiv 0903.5143.
sage.combinat.perfect_matching.PerfectMatching

A perfect matching.

A perfect matching of a set \(X\) is a set partition of \(X\) where all parts have size 2.

A perfect matching can be created from a list of pairs or from a fixed point-free involution as follows:

sage: m = PerfectMatching([('a','e'),('b','c'),('d','f')]);m
[('a', 'e'), ('b', 'c'), ('d', 'f')]
sage: n = PerfectMatching([3,8,1,7,6,5,4,2]);n
[(1, 3), (2, 8), (4, 7), (5, 6)]
sage: isinstance(m,PerfectMatching)
True

The parent, which is the set of perfect matchings of the ground set, is automatically created:

sage: n.parent()
Perfect matchings of {1, 2, 3, 4, 5, 6, 7, 8}

If the ground set is ordered, one can, for example, ask if the matching is non crossing:

sage: PerfectMatching([(1, 4), (2, 3), (5, 6)]).is_noncrossing()
True
sage.combinat.perfect_matching.PerfectMatchings

Perfect matchings of a ground set.

INPUT:

  • s – an itegerable of hashable objects or an integer

EXAMPLES:

If the argument s is an integer \(n\), it will be transformed into the set \(\{1, \ldots, n\}\):

sage: M = PerfectMatchings(6); M
Perfect matchings of {1, 2, 3, 4, 5, 6}
sage: PerfectMatchings([-1, -3, 1, 2])
Perfect matchings of {1, 2, -3, -1}

One can ask for the list, the cardinality or an element of a set of perfect matching:

sage: PerfectMatchings(4).list()
[[(1, 2), (3, 4)], [(1, 3), (2, 4)], [(1, 4), (2, 3)]]
sage: PerfectMatchings(8).cardinality()
105
sage: M = PerfectMatchings(('a', 'e', 'b', 'f', 'c', 'd'))
sage: M.an_element()
[('a', 'c'), ('b', 'e'), ('d', 'f')]
sage: all(PerfectMatchings(i).an_element() in PerfectMatchings(i)
....:     for i in range(2,11,2))
True
sage: S = PerfectMatchings(4)
sage: elt = S([[1,3],[2,4]]); elt
[(1, 3), (2, 4)]
sage: S = PerfectMatchings([])
sage: S([])
[]