- FindStat

edit this statistic or download as text // json

Identifier

St000789: Perfect matchings ⟶ ℤ

Values

[(1,2)] => 1

[(1,2),(3,4)] => 1

[(1,3),(2,4)] => 1

[(1,4),(2,3)] => 1

[(1,2),(3,4),(5,6)] => 1

[(1,3),(2,4),(5,6)] => 2

[(1,4),(2,3),(5,6)] => 2

[(1,5),(2,3),(4,6)] => 2

[(1,6),(2,3),(4,5)] => 1

[(1,6),(2,4),(3,5)] => 2

[(1,5),(2,4),(3,6)] => 2

[(1,4),(2,5),(3,6)] => 1

[(1,3),(2,5),(4,6)] => 1

[(1,2),(3,5),(4,6)] => 2

[(1,2),(3,6),(4,5)] => 2

[(1,3),(2,6),(4,5)] => 2

[(1,4),(2,6),(3,5)] => 2

[(1,5),(2,6),(3,4)] => 2

[(1,6),(2,5),(3,4)] => 1

[(1,2),(3,4),(5,6),(7,8)] => 1

[(1,3),(2,4),(5,6),(7,8)] => 3

[(1,4),(2,3),(5,6),(7,8)] => 3

[(1,5),(2,3),(4,6),(7,8)] => 6

[(1,6),(2,3),(4,5),(7,8)] => 3

[(1,7),(2,3),(4,5),(6,8)] => 3

[(1,8),(2,3),(4,5),(6,7)] => 1

[(1,8),(2,4),(3,5),(6,7)] => 6

[(1,7),(2,4),(3,5),(6,8)] => 8

[(1,6),(2,4),(3,5),(7,8)] => 4

[(1,5),(2,4),(3,6),(7,8)] => 4

[(1,4),(2,5),(3,6),(7,8)] => 2

[(1,3),(2,5),(4,6),(7,8)] => 3

[(1,2),(3,5),(4,6),(7,8)] => 3

[(1,2),(3,6),(4,5),(7,8)] => 3

[(1,3),(2,6),(4,5),(7,8)] => 6

[(1,4),(2,6),(3,5),(7,8)] => 4

[(1,5),(2,6),(3,4),(7,8)] => 4

[(1,6),(2,5),(3,4),(7,8)] => 2

[(1,7),(2,5),(3,4),(6,8)] => 6

[(1,8),(2,5),(3,4),(6,7)] => 2

[(1,8),(2,6),(3,4),(5,7)] => 3

[(1,7),(2,6),(3,4),(5,8)] => 5

[(1,6),(2,7),(3,4),(5,8)] => 5

[(1,5),(2,7),(3,4),(6,8)] => 8

[(1,4),(2,7),(3,5),(6,8)] => 6

[(1,3),(2,7),(4,5),(6,8)] => 3

[(1,2),(3,7),(4,5),(6,8)] => 6

[(1,2),(3,8),(4,5),(6,7)] => 3

[(1,3),(2,8),(4,5),(6,7)] => 3

[(1,4),(2,8),(3,5),(6,7)] => 8

[(1,5),(2,8),(3,4),(6,7)] => 6

[(1,6),(2,8),(3,4),(5,7)] => 5

[(1,7),(2,8),(3,4),(5,6)] => 3

[(1,8),(2,7),(3,4),(5,6)] => 1

[(1,8),(2,7),(3,5),(4,6)] => 3

[(1,7),(2,8),(3,5),(4,6)] => 5

[(1,6),(2,8),(3,5),(4,7)] => 6

[(1,5),(2,8),(3,6),(4,7)] => 5

[(1,4),(2,8),(3,6),(5,7)] => 5

[(1,3),(2,8),(4,6),(5,7)] => 8

[(1,2),(3,8),(4,6),(5,7)] => 4

[(1,2),(3,7),(4,6),(5,8)] => 4

[(1,3),(2,7),(4,6),(5,8)] => 6

[(1,4),(2,7),(3,6),(5,8)] => 3

[(1,5),(2,7),(3,6),(4,8)] => 3

[(1,6),(2,7),(3,5),(4,8)] => 5

[(1,7),(2,6),(3,5),(4,8)] => 6

[(1,8),(2,6),(3,5),(4,7)] => 5

[(1,8),(2,5),(3,6),(4,7)] => 6

[(1,7),(2,5),(3,6),(4,8)] => 5

[(1,6),(2,5),(3,7),(4,8)] => 3

[(1,5),(2,6),(3,7),(4,8)] => 1

[(1,4),(2,6),(3,7),(5,8)] => 1

[(1,3),(2,6),(4,7),(5,8)] => 2

[(1,2),(3,6),(4,7),(5,8)] => 2

[(1,2),(3,5),(4,7),(6,8)] => 3

[(1,3),(2,5),(4,7),(6,8)] => 1

[(1,4),(2,5),(3,7),(6,8)] => 2

[(1,5),(2,4),(3,7),(6,8)] => 6

[(1,6),(2,4),(3,7),(5,8)] => 3

[(1,7),(2,4),(3,6),(5,8)] => 5

[(1,8),(2,4),(3,6),(5,7)] => 5

[(1,8),(2,3),(4,6),(5,7)] => 6

[(1,7),(2,3),(4,6),(5,8)] => 8

[(1,6),(2,3),(4,7),(5,8)] => 6

[(1,5),(2,3),(4,7),(6,8)] => 3

[(1,4),(2,3),(5,7),(6,8)] => 6

[(1,3),(2,4),(5,7),(6,8)] => 3

[(1,2),(3,4),(5,7),(6,8)] => 3

[(1,2),(3,4),(5,8),(6,7)] => 3

[(1,3),(2,4),(5,8),(6,7)] => 6

[(1,4),(2,3),(5,8),(6,7)] => 3

[(1,5),(2,3),(4,8),(6,7)] => 3

[(1,6),(2,3),(4,8),(5,7)] => 8

[(1,7),(2,3),(4,8),(5,6)] => 6

[(1,8),(2,3),(4,7),(5,6)] => 2

[(1,8),(2,4),(3,7),(5,6)] => 3

[(1,7),(2,4),(3,8),(5,6)] => 5

[(1,6),(2,4),(3,8),(5,7)] => 5

[(1,5),(2,4),(3,8),(6,7)] => 8

[(1,4),(2,5),(3,8),(6,7)] => 6

>>> Load all 1200 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The number of crossing-similar perfect matchings of a perfect matching.
Consider the infinite tree $T$ defined in [1] as follows. $T$ has the perfect matchings on $\{1,\dots,2n\}$ on level $n$, with children obtained by inserting an arc with opener $1$. For example, the matching $[(1,2)]$ has the three children $[(1,2),(3,4)]$, $[(1,3),(2,4)]$ and $[(1,4),(2,3)]$.
Two perfect matchings $M$ and $N$ on $\{1,\dots,2n\}$ are nesting-similar, if the distribution of the number of crossings agrees on all levels of the subtrees of $T$ rooted at $M$ and $N$.
[thm 1.2, 1] shows that to find out whether $M$ and $N$ are crossing-similar, it is enough to check that $M$ and $N$ have the same number of crossings, and that the distribution of crossings agrees for their direct children.
[thm 3.3, 1], see also [2], gives the number of equivalence classes of crossing-similar matchings with $n$ arcs as $$2^{n-2}\left(\binom{n}{2}+2\right).$$

References

[1] Klazar, M. On identities concerning the numbers of crossings and nestings of two edges in matchings MathSciNet:2272241 arXiv:math/0503012
[2] a(n) = 2^(n-2)*(C(n,2)+2). OEIS:A104270

Code

def KlazarTM1(m):
    """
    For a matching m return T(m,1) of Klazar's tree.

    sage: [m for m in KlazarTM1(PerfectMatching([(1,2)]))]
    [[(1, 2), (3, 4)], [(1, 3), (2, 4)], [(1, 4), (2, 3)]]

    """
    for i in range(m.size()+1):
        m_new = [(e+1 if e < 1+i else e+2,
                  f+1 if f < 1+i else f+2) for (e,f) in m]
        m_new.append((1,2+i))
        yield PerfectMatching(sorted(m_new))

@cached_function
def crossing_similar_classes(n):
    """Return a set partition of the matchings with 2n arcs that are
    crossing_similar.  """
    d = dict()
    for m in PerfectMatchings(n):
        dist = (m.number_of_crossings(),
                tuple(sorted(k.number_of_crossings() for k in KlazarTM1(m))))
        d[dist] = d.get(dist, []) + [m]
    return d

def statistic(m):
    dist = (m.number_of_crossings(),
            tuple(sorted(k.number_of_crossings() for k in KlazarTM1(m))))
    return len(crossing_similar_classes(m.size())[dist])

Created

Apr 23, 2017 at 09:53 by Martin Rubey

Updated

Apr 23, 2017 at 10:48 by Martin Rubey