PerfectMatchings
A name from the enumeratio catalogue with no kernel of its own yet; this page carries its crosswalk only.
Catalogued in the enumeratio database, with crosswalk rows in oeis, sage, wikipedia; not yet written up here.
✓ checked against that system · ! checked, with disagreements (hover a chip)Wikipedia
Perfect matchingMathWorld1-FactorWikidataQ99567093OEISA001147✓SageMathsage.combinat.perfect_matching.PerfectMatchings(k)PerfectMatchings(...)Catalogued in the enumeratio database, with crosswalk rows in oeis, sage, wikipedia; not yet written up here.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<perfect_matching> | combinatorics | always |
Definition
Epsil, as the implementation runs it.
count(_n)
0 if _n < 0 else Fold(Function(pca * (2pct - 1), pca, pct), 1, Range(1, _n, 1))unrank(_n, _r)
Apply(
(pm: list<integer>) => Apply(
(pl: list<integer>) => Map(
Function([
pl[pk],
pm[pl[pk]],
], pk),
Range(1, _n, 1),
),
Filter(Range(1, 2 * _n, 1), Function(pf <
pm[pf], pf)),
),
Apply(
(ps_init: list<integer>) => Fold((ps: list<integer>, pi) => Apply(
(ps_next: list<integer>) => ps_next,
Apply(
(pd: integer) => Apply(
(pp: integer) => Apply(
(pq: integer) => ReplaceAt(ReplaceAt(ps, pp, pq), pq, pp),
Apply((pn_init: list<integer>) => Fold(
(pn: list<integer>, pw) => Apply(
(pn_next: list<integer>) => pn_next,
([pn[1] + 1, pw] if pn[1] == pd else [pn[1] + 1, pn[2]]) if pp < pw &&
ps[pw] == 0 else pn,
),
pn_init,
Range(1, 2 * _n, 1),
), [0, 0])[2],
),
Fold(
Function(py if pa == 0 &&
ps[py] == 0 else pa, pa, py),
0,
Range(1, 2 * _n, 1),
),
),
(_r -
_r %
Fold(
Function(poa *
(2pot - 1), poa, pot),
1,
Range(1, _n - pi, 1),
)) /
Fold(
Function(poa *
(2pot - 1), poa, pot),
1,
Range(1, _n - pi, 1),
) %
(2 *
(_n - pi) +
1),
),
), ps_init, Range(1, _n, 1)),
Map(Function(0, pz0), Range(1, 2 * _n, 1)),
),
)rank(_n, _x)
Apply(
(pt: list<integer>) => Fold(
Function(pa + (Apply(
(pb: integer) => Fold(
Function(py +
(1 if px < pt[pu] else 0), py, pu),
0,
Range(
px + 1,
pt[px] - 1,
1,
),
) *
Fold(
Function(pra *
(2prt - 1), pra, prt),
1,
Range(1, pb, 1),
),
_n - Fold(
Function(pc +
(1 if pz < pt[pz] else 0), pc, pz),
0,
Range(
1,
px -
1,
1,
),
) - 1,
) if px < pt[px] else 0), pa, px),
0,
Range(1, 2 * _n, 1),
),
Apply((pmn: list<integer>) => Apply(
(pmx: list<integer>) => Map(
Function(Fold(
Function(
pmx[pj] if pmn[pj] == pp else pmn[pj] if pmx[pj] == pp else pq,
pq,
pj,
),
0,
Range(1, Length(_x), 1),
), pp),
Range(
1,
2 * _n,
1,
),
),
Map(Function(Max(blk), blk), _x),
), Map(Function(Min(blk), blk), _x)),
)valid(_n, _x)
Length(_x) == _n && Fold(
Function(ok_blk && Length(blk) == 2, ok_blk, blk),
True,
_x,
) && Apply((flat: list<integer>) => Fold(
Function(ok_y &&
Contains(flat, y), ok_y, y),
True,
Range(
1,
2 * _n,
1,
),
), Flatten(_x))Statistics
On PerfectMatching, called as CombinatorialStat(x, "Name").
- AlignedPairCountSt000719Pairs of pairs (a, b), (c, d) with a < b < c < d.
- ClosersBelowLargestOpenerSt000840The pairs whose larger point is below the largest opener, the larger point of the pair opening last.
- CrossingsPlusTwiceNestingsSt000043The crossings plus twice the nestings.
- EarlyCloserPairCountSt001044Pairs whose larger point is at most n + 1, for a matching of 2n points.
- IdentityMatchingEdgeCountSt001997Pairs {2k - 1, 2k}: the edges shared with the matching 12, 34, 56, ....
- MaximalNestingCountSt001046The most pairs that nest one pair: the largest number of pairs (a, b) with a < c and d < b, over the pairs (c, d).
- MaximalRightCrossingCountSt001047The most pairs (c, d) with a < c < b < d, over the pairs (a, b): arcs that cross a given arc at its right end.
- PropagatingNumberSt000819Pairs with one point among the first n and the other among the last n, for a matching of 2n points.
Maps
Into and out of PerfectMatching, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
11 more in FindStat, not implemented here
- Mp00058PerfectMatching → PermutationInjectionGraded mapto permutation
- Mp00092PerfectMatching → SetPartitionInjectionGraded mapto set partition
- Mp00098AlternatingSignMatrix → PerfectMatchingGraded maplink pattern
- Mp00113PerfectMatching → PerfectMatchingBijectionGraded mapInvolutionreverse
- Mp00116PerfectMatching → PerfectMatchingBijectionGraded mapInvolutionKasraoui-Zeng
- Mp00144PerfectMatching → PerfectMatchingBijectionGraded maprotation
- Mp00145PerfectMatching → PerfectMatchingBijectionGraded mapinverse rotation
- Mp00146DyckPath → PerfectMatchingInjectionGraded mapto tunnel matching
- Mp00150PerfectMatching → DyckPathSurjectionGraded mapto Dyck path
- Mp00165PerfectMatching → PerfectMatchingGraded mapInvolutionChen Deng Du Stanley Yan
- Mp00283PerfectMatching → PermutationInjectionGraded mapnon-nesting-exceedence permutation