- FindStat

Identifier

Mp00080: Set partitions —to permutation⟶ Permutations
Mp00127: Permutations —left-to-right-maxima to Dyck path⟶ Dyck paths
Mp00146: Dyck paths —to tunnel matching⟶ Perfect matchings
St000788: Perfect matchings ⟶ ℤ

Values

{{1}} => [1] => [1,0] => [(1,2)] => 1
{{1,2}} => [2,1] => [1,1,0,0] => [(1,4),(2,3)] => 1
{{1},{2}} => [1,2] => [1,0,1,0] => [(1,2),(3,4)] => 1
{{1,2,3}} => [2,3,1] => [1,1,0,1,0,0] => [(1,6),(2,3),(4,5)] => 1
{{1,2},{3}} => [2,1,3] => [1,1,0,0,1,0] => [(1,4),(2,3),(5,6)] => 1
{{1,3},{2}} => [3,2,1] => [1,1,1,0,0,0] => [(1,6),(2,5),(3,4)] => 1
{{1},{2,3}} => [1,3,2] => [1,0,1,1,0,0] => [(1,2),(3,6),(4,5)] => 1
{{1},{2},{3}} => [1,2,3] => [1,0,1,0,1,0] => [(1,2),(3,4),(5,6)] => 1
{{1,2,3,4}} => [2,3,4,1] => [1,1,0,1,0,1,0,0] => [(1,8),(2,3),(4,5),(6,7)] => 1
{{1,2,3},{4}} => [2,3,1,4] => [1,1,0,1,0,0,1,0] => [(1,6),(2,3),(4,5),(7,8)] => 1
{{1,2,4},{3}} => [2,4,3,1] => [1,1,0,1,1,0,0,0] => [(1,8),(2,3),(4,7),(5,6)] => 1
{{1,2},{3,4}} => [2,1,4,3] => [1,1,0,0,1,1,0,0] => [(1,4),(2,3),(5,8),(6,7)] => 1
{{1,2},{3},{4}} => [2,1,3,4] => [1,1,0,0,1,0,1,0] => [(1,4),(2,3),(5,6),(7,8)] => 1
{{1,3,4},{2}} => [3,2,4,1] => [1,1,1,0,0,1,0,0] => [(1,8),(2,5),(3,4),(6,7)] => 1
{{1,3},{2,4}} => [3,4,1,2] => [1,1,1,0,1,0,0,0] => [(1,8),(2,7),(3,4),(5,6)] => 1
{{1,3},{2},{4}} => [3,2,1,4] => [1,1,1,0,0,0,1,0] => [(1,6),(2,5),(3,4),(7,8)] => 1
{{1,4},{2,3}} => [4,3,2,1] => [1,1,1,1,0,0,0,0] => [(1,8),(2,7),(3,6),(4,5)] => 1
{{1},{2,3,4}} => [1,3,4,2] => [1,0,1,1,0,1,0,0] => [(1,2),(3,8),(4,5),(6,7)] => 1
{{1},{2,3},{4}} => [1,3,2,4] => [1,0,1,1,0,0,1,0] => [(1,2),(3,6),(4,5),(7,8)] => 1
{{1,4},{2},{3}} => [4,2,3,1] => [1,1,1,1,0,0,0,0] => [(1,8),(2,7),(3,6),(4,5)] => 1
{{1},{2,4},{3}} => [1,4,3,2] => [1,0,1,1,1,0,0,0] => [(1,2),(3,8),(4,7),(5,6)] => 1
{{1},{2},{3,4}} => [1,2,4,3] => [1,0,1,0,1,1,0,0] => [(1,2),(3,4),(5,8),(6,7)] => 1
{{1},{2},{3},{4}} => [1,2,3,4] => [1,0,1,0,1,0,1,0] => [(1,2),(3,4),(5,6),(7,8)] => 1
{{1,2,3,4,5}} => [2,3,4,5,1] => [1,1,0,1,0,1,0,1,0,0] => [(1,10),(2,3),(4,5),(6,7),(8,9)] => 1
{{1,2,3,4},{5}} => [2,3,4,1,5] => [1,1,0,1,0,1,0,0,1,0] => [(1,8),(2,3),(4,5),(6,7),(9,10)] => 1
{{1,2,3,5},{4}} => [2,3,5,4,1] => [1,1,0,1,0,1,1,0,0,0] => [(1,10),(2,3),(4,5),(6,9),(7,8)] => 1
{{1,2,3},{4,5}} => [2,3,1,5,4] => [1,1,0,1,0,0,1,1,0,0] => [(1,6),(2,3),(4,5),(7,10),(8,9)] => 1
{{1,2,3},{4},{5}} => [2,3,1,4,5] => [1,1,0,1,0,0,1,0,1,0] => [(1,6),(2,3),(4,5),(7,8),(9,10)] => 1
{{1,2,4,5},{3}} => [2,4,3,5,1] => [1,1,0,1,1,0,0,1,0,0] => [(1,10),(2,3),(4,7),(5,6),(8,9)] => 1
{{1,2,4},{3,5}} => [2,4,5,1,3] => [1,1,0,1,1,0,1,0,0,0] => [(1,10),(2,3),(4,9),(5,6),(7,8)] => 1
{{1,2,4},{3},{5}} => [2,4,3,1,5] => [1,1,0,1,1,0,0,0,1,0] => [(1,8),(2,3),(4,7),(5,6),(9,10)] => 1
{{1,2,5},{3,4}} => [2,5,4,3,1] => [1,1,0,1,1,1,0,0,0,0] => [(1,10),(2,3),(4,9),(5,8),(6,7)] => 1
{{1,2},{3,4,5}} => [2,1,4,5,3] => [1,1,0,0,1,1,0,1,0,0] => [(1,4),(2,3),(5,10),(6,7),(8,9)] => 1
{{1,2},{3,4},{5}} => [2,1,4,3,5] => [1,1,0,0,1,1,0,0,1,0] => [(1,4),(2,3),(5,8),(6,7),(9,10)] => 1
{{1,2,5},{3},{4}} => [2,5,3,4,1] => [1,1,0,1,1,1,0,0,0,0] => [(1,10),(2,3),(4,9),(5,8),(6,7)] => 1
{{1,2},{3,5},{4}} => [2,1,5,4,3] => [1,1,0,0,1,1,1,0,0,0] => [(1,4),(2,3),(5,10),(6,9),(7,8)] => 1
{{1,2},{3},{4,5}} => [2,1,3,5,4] => [1,1,0,0,1,0,1,1,0,0] => [(1,4),(2,3),(5,6),(7,10),(8,9)] => 1
{{1,2},{3},{4},{5}} => [2,1,3,4,5] => [1,1,0,0,1,0,1,0,1,0] => [(1,4),(2,3),(5,6),(7,8),(9,10)] => 1
{{1,3,4,5},{2}} => [3,2,4,5,1] => [1,1,1,0,0,1,0,1,0,0] => [(1,10),(2,5),(3,4),(6,7),(8,9)] => 1
{{1,3,4},{2,5}} => [3,5,4,1,2] => [1,1,1,0,1,1,0,0,0,0] => [(1,10),(2,9),(3,4),(5,8),(6,7)] => 1
{{1,3,4},{2},{5}} => [3,2,4,1,5] => [1,1,1,0,0,1,0,0,1,0] => [(1,8),(2,5),(3,4),(6,7),(9,10)] => 1
{{1,3,5},{2,4}} => [3,4,5,2,1] => [1,1,1,0,1,0,1,0,0,0] => [(1,10),(2,9),(3,4),(5,6),(7,8)] => 1
{{1,3},{2,4,5}} => [3,4,1,5,2] => [1,1,1,0,1,0,0,1,0,0] => [(1,10),(2,7),(3,4),(5,6),(8,9)] => 1
{{1,3},{2,4},{5}} => [3,4,1,2,5] => [1,1,1,0,1,0,0,0,1,0] => [(1,8),(2,7),(3,4),(5,6),(9,10)] => 1
{{1,3,5},{2},{4}} => [3,2,5,4,1] => [1,1,1,0,0,1,1,0,0,0] => [(1,10),(2,5),(3,4),(6,9),(7,8)] => 1
{{1,3},{2,5},{4}} => [3,5,1,4,2] => [1,1,1,0,1,1,0,0,0,0] => [(1,10),(2,9),(3,4),(5,8),(6,7)] => 1
{{1,3},{2},{4,5}} => [3,2,1,5,4] => [1,1,1,0,0,0,1,1,0,0] => [(1,6),(2,5),(3,4),(7,10),(8,9)] => 1
{{1,3},{2},{4},{5}} => [3,2,1,4,5] => [1,1,1,0,0,0,1,0,1,0] => [(1,6),(2,5),(3,4),(7,8),(9,10)] => 1
{{1,4,5},{2,3}} => [4,3,2,5,1] => [1,1,1,1,0,0,0,1,0,0] => [(1,10),(2,7),(3,6),(4,5),(8,9)] => 1
{{1,4},{2,3,5}} => [4,3,5,1,2] => [1,1,1,1,0,0,1,0,0,0] => [(1,10),(2,9),(3,6),(4,5),(7,8)] => 1
{{1,4},{2,3},{5}} => [4,3,2,1,5] => [1,1,1,1,0,0,0,0,1,0] => [(1,8),(2,7),(3,6),(4,5),(9,10)] => 1
{{1,5},{2,3,4}} => [5,3,4,2,1] => [1,1,1,1,1,0,0,0,0,0] => [(1,10),(2,9),(3,8),(4,7),(5,6)] => 1
{{1},{2,3,4,5}} => [1,3,4,5,2] => [1,0,1,1,0,1,0,1,0,0] => [(1,2),(3,10),(4,5),(6,7),(8,9)] => 1
{{1},{2,3,4},{5}} => [1,3,4,2,5] => [1,0,1,1,0,1,0,0,1,0] => [(1,2),(3,8),(4,5),(6,7),(9,10)] => 1
{{1,5},{2,3},{4}} => [5,3,2,4,1] => [1,1,1,1,1,0,0,0,0,0] => [(1,10),(2,9),(3,8),(4,7),(5,6)] => 1
{{1},{2,3,5},{4}} => [1,3,5,4,2] => [1,0,1,1,0,1,1,0,0,0] => [(1,2),(3,10),(4,5),(6,9),(7,8)] => 1
{{1},{2,3},{4,5}} => [1,3,2,5,4] => [1,0,1,1,0,0,1,1,0,0] => [(1,2),(3,6),(4,5),(7,10),(8,9)] => 1
{{1},{2,3},{4},{5}} => [1,3,2,4,5] => [1,0,1,1,0,0,1,0,1,0] => [(1,2),(3,6),(4,5),(7,8),(9,10)] => 1
{{1,4,5},{2},{3}} => [4,2,3,5,1] => [1,1,1,1,0,0,0,1,0,0] => [(1,10),(2,7),(3,6),(4,5),(8,9)] => 1
{{1,4},{2,5},{3}} => [4,5,3,1,2] => [1,1,1,1,0,1,0,0,0,0] => [(1,10),(2,9),(3,8),(4,5),(6,7)] => 1
{{1,4},{2},{3,5}} => [4,2,5,1,3] => [1,1,1,1,0,0,1,0,0,0] => [(1,10),(2,9),(3,6),(4,5),(7,8)] => 1
{{1,4},{2},{3},{5}} => [4,2,3,1,5] => [1,1,1,1,0,0,0,0,1,0] => [(1,8),(2,7),(3,6),(4,5),(9,10)] => 1
{{1,5},{2,4},{3}} => [5,4,3,2,1] => [1,1,1,1,1,0,0,0,0,0] => [(1,10),(2,9),(3,8),(4,7),(5,6)] => 1
{{1},{2,4,5},{3}} => [1,4,3,5,2] => [1,0,1,1,1,0,0,1,0,0] => [(1,2),(3,10),(4,7),(5,6),(8,9)] => 1
{{1},{2,4},{3,5}} => [1,4,5,2,3] => [1,0,1,1,1,0,1,0,0,0] => [(1,2),(3,10),(4,9),(5,6),(7,8)] => 1
{{1},{2,4},{3},{5}} => [1,4,3,2,5] => [1,0,1,1,1,0,0,0,1,0] => [(1,2),(3,8),(4,7),(5,6),(9,10)] => 1
{{1,5},{2},{3,4}} => [5,2,4,3,1] => [1,1,1,1,1,0,0,0,0,0] => [(1,10),(2,9),(3,8),(4,7),(5,6)] => 1
{{1},{2,5},{3,4}} => [1,5,4,3,2] => [1,0,1,1,1,1,0,0,0,0] => [(1,2),(3,10),(4,9),(5,8),(6,7)] => 1
{{1},{2},{3,4,5}} => [1,2,4,5,3] => [1,0,1,0,1,1,0,1,0,0] => [(1,2),(3,4),(5,10),(6,7),(8,9)] => 1
{{1},{2},{3,4},{5}} => [1,2,4,3,5] => [1,0,1,0,1,1,0,0,1,0] => [(1,2),(3,4),(5,8),(6,7),(9,10)] => 1
{{1,5},{2},{3},{4}} => [5,2,3,4,1] => [1,1,1,1,1,0,0,0,0,0] => [(1,10),(2,9),(3,8),(4,7),(5,6)] => 1
{{1},{2,5},{3},{4}} => [1,5,3,4,2] => [1,0,1,1,1,1,0,0,0,0] => [(1,2),(3,10),(4,9),(5,8),(6,7)] => 1
{{1},{2},{3,5},{4}} => [1,2,5,4,3] => [1,0,1,0,1,1,1,0,0,0] => [(1,2),(3,4),(5,10),(6,9),(7,8)] => 1
{{1},{2},{3},{4,5}} => [1,2,3,5,4] => [1,0,1,0,1,0,1,1,0,0] => [(1,2),(3,4),(5,6),(7,10),(8,9)] => 1
{{1},{2},{3},{4},{5}} => [1,2,3,4,5] => [1,0,1,0,1,0,1,0,1,0] => [(1,2),(3,4),(5,6),(7,8),(9,10)] => 1
{{1},{2},{3,4,5,6}} => [1,2,4,5,6,3] => [1,0,1,0,1,1,0,1,0,1,0,0] => [(1,2),(3,4),(5,12),(6,7),(8,9),(10,11)] => 1
{{1},{2},{3,4,5},{6}} => [1,2,4,5,3,6] => [1,0,1,0,1,1,0,1,0,0,1,0] => [(1,2),(3,4),(5,10),(6,7),(8,9),(11,12)] => 1
{{1},{2},{3,4,6},{5}} => [1,2,4,6,5,3] => [1,0,1,0,1,1,0,1,1,0,0,0] => [(1,2),(3,4),(5,12),(6,7),(8,11),(9,10)] => 1
{{1},{2},{3,4},{5,6}} => [1,2,4,3,6,5] => [1,0,1,0,1,1,0,0,1,1,0,0] => [(1,2),(3,4),(5,8),(6,7),(9,12),(10,11)] => 1
{{1},{2},{3,4},{5},{6}} => [1,2,4,3,5,6] => [1,0,1,0,1,1,0,0,1,0,1,0] => [(1,2),(3,4),(5,8),(6,7),(9,10),(11,12)] => 1
{{1},{2},{3,5,6},{4}} => [1,2,5,4,6,3] => [1,0,1,0,1,1,1,0,0,1,0,0] => [(1,2),(3,4),(5,12),(6,9),(7,8),(10,11)] => 1
{{1},{2},{3,5},{4,6}} => [1,2,5,6,3,4] => [1,0,1,0,1,1,1,0,1,0,0,0] => [(1,2),(3,4),(5,12),(6,11),(7,8),(9,10)] => 1
{{1},{2},{3,5},{4},{6}} => [1,2,5,4,3,6] => [1,0,1,0,1,1,1,0,0,0,1,0] => [(1,2),(3,4),(5,10),(6,9),(7,8),(11,12)] => 1
{{1},{2},{3,6},{4,5}} => [1,2,6,5,4,3] => [1,0,1,0,1,1,1,1,0,0,0,0] => [(1,2),(3,4),(5,12),(6,11),(7,10),(8,9)] => 1
{{1},{2},{3},{4,5,6}} => [1,2,3,5,6,4] => [1,0,1,0,1,0,1,1,0,1,0,0] => [(1,2),(3,4),(5,6),(7,12),(8,9),(10,11)] => 1
{{1},{2},{3},{4,5},{6}} => [1,2,3,5,4,6] => [1,0,1,0,1,0,1,1,0,0,1,0] => [(1,2),(3,4),(5,6),(7,10),(8,9),(11,12)] => 1
{{1},{2},{3,6},{4},{5}} => [1,2,6,4,5,3] => [1,0,1,0,1,1,1,1,0,0,0,0] => [(1,2),(3,4),(5,12),(6,11),(7,10),(8,9)] => 1
{{1},{2},{3},{4,6},{5}} => [1,2,3,6,5,4] => [1,0,1,0,1,0,1,1,1,0,0,0] => [(1,2),(3,4),(5,6),(7,12),(8,11),(9,10)] => 1
{{1},{2},{3},{4},{5,6}} => [1,2,3,4,6,5] => [1,0,1,0,1,0,1,0,1,1,0,0] => [(1,2),(3,4),(5,6),(7,8),(9,12),(10,11)] => 1
{{1},{2},{3},{4},{5},{6}} => [1,2,3,4,5,6] => [1,0,1,0,1,0,1,0,1,0,1,0] => [(1,2),(3,4),(5,6),(7,8),(9,10),(11,12)] => 1

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

$F_{1} = q$

$F_{2} = 2\ q$

$F_{3} = 5\ q$

$F_{4} = 15\ q$

$F_{5} = 52\ q$

Description

The number of nesting-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 nestings 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 nesting-similar, it is enough to check that

$M$ and

$N$ have the same number of nestings, and that the distribution of nestings agrees for their direct children.
[thm 3.5, 1], see also [2], gives the number of equivalence classes of nesting-similar matchings with

$n$ arcs as

$2\cdot 4^{n-1} - \frac{3n-1}{2n+2}\binom{2n}{n}.$ [prop 3.6, 1] has further interpretations of this number.

Map

to permutation

Description

Sends the set partition to the permutation obtained by considering the blocks as increasing cycles.

Map

to tunnel matching

Description

Sends a Dyck path of semilength n to the noncrossing perfect matching given by matching an up-step with the corresponding down-step.
This is, for a Dyck path

$D$ of semilength

$n$ , the perfect matching of

$\{1,\dots,2n\}$ with

$i < j$ being matched if

$D_i$ is an up-step and

$D_j$ is the down-step connected to

$D_i$ by a tunnel.

Map

left-to-right-maxima to Dyck path

Description

The left-to-right maxima of a permutation as a Dyck path.
Let

$(c_1, \dots, c_k)$ be the rise composition Mp00102rise composition of the path. Then the corresponding left-to-right maxima are

$c_1, c_1+c_2, \dots, c_1+\dots+c_k$ .
Restricted to 321-avoiding permutations, this is the inverse of Mp00119to 321-avoiding permutation (Krattenthaler), restricted to 312-avoiding permutations, this is the inverse of Mp00031to 312-avoiding permutation.