Identifier
-
Mp00296:
Dyck paths
—Knuth-Krattenthaler⟶
Dyck paths
Mp00222: Dyck paths —peaks-to-valleys⟶ Dyck paths
Mp00146: Dyck paths —to tunnel matching⟶ Perfect matchings
St000787: Perfect matchings ⟶ ℤ
Values
[1,0] => [1,0] => [1,0] => [(1,2)] => 0
[1,0,1,0] => [1,1,0,0] => [1,0,1,0] => [(1,2),(3,4)] => 0
[1,1,0,0] => [1,0,1,0] => [1,1,0,0] => [(1,4),(2,3)] => 0
[1,0,1,0,1,0] => [1,1,1,0,0,0] => [1,1,0,1,0,0] => [(1,6),(2,3),(4,5)] => 0
[1,0,1,1,0,0] => [1,1,0,1,0,0] => [1,0,1,0,1,0] => [(1,2),(3,4),(5,6)] => 0
[1,1,0,0,1,0] => [1,0,1,0,1,0] => [1,1,1,0,0,0] => [(1,6),(2,5),(3,4)] => 0
[1,1,0,1,0,0] => [1,0,1,1,0,0] => [1,1,0,0,1,0] => [(1,4),(2,3),(5,6)] => 0
[1,1,1,0,0,0] => [1,1,0,0,1,0] => [1,0,1,1,0,0] => [(1,2),(3,6),(4,5)] => 0
[1,0,1,0,1,0,1,0] => [1,1,1,1,0,0,0,0] => [1,1,1,0,1,0,0,0] => [(1,8),(2,7),(3,4),(5,6)] => 0
[1,0,1,0,1,1,0,0] => [1,1,1,0,1,0,0,0] => [1,1,0,1,0,1,0,0] => [(1,8),(2,3),(4,5),(6,7)] => 0
[1,0,1,1,0,0,1,0] => [1,1,0,1,0,1,0,0] => [1,0,1,0,1,0,1,0] => [(1,2),(3,4),(5,6),(7,8)] => 0
[1,0,1,1,0,1,0,0] => [1,1,0,1,1,0,0,0] => [1,0,1,1,0,1,0,0] => [(1,2),(3,8),(4,5),(6,7)] => 0
[1,0,1,1,1,0,0,0] => [1,1,1,0,0,1,0,0] => [1,1,0,1,0,0,1,0] => [(1,6),(2,3),(4,5),(7,8)] => 0
[1,1,0,0,1,0,1,0] => [1,0,1,1,0,0,1,0] => [1,1,0,0,1,1,0,0] => [(1,4),(2,3),(5,8),(6,7)] => 0
[1,1,0,0,1,1,0,0] => [1,0,1,0,1,0,1,0] => [1,1,1,1,0,0,0,0] => [(1,8),(2,7),(3,6),(4,5)] => 0
[1,1,0,1,0,0,1,0] => [1,0,1,1,0,1,0,0] => [1,1,0,0,1,0,1,0] => [(1,4),(2,3),(5,6),(7,8)] => 0
[1,1,0,1,0,1,0,0] => [1,0,1,1,1,0,0,0] => [1,1,1,0,0,1,0,0] => [(1,8),(2,5),(3,4),(6,7)] => 0
[1,1,0,1,1,0,0,0] => [1,0,1,0,1,1,0,0] => [1,1,1,0,0,0,1,0] => [(1,6),(2,5),(3,4),(7,8)] => 0
[1,1,1,0,0,0,1,0] => [1,1,0,1,0,0,1,0] => [1,0,1,0,1,1,0,0] => [(1,2),(3,4),(5,8),(6,7)] => 0
[1,1,1,0,0,1,0,0] => [1,1,0,0,1,0,1,0] => [1,0,1,1,1,0,0,0] => [(1,2),(3,8),(4,7),(5,6)] => 0
[1,1,1,0,1,0,0,0] => [1,1,0,0,1,1,0,0] => [1,0,1,1,0,0,1,0] => [(1,2),(3,6),(4,5),(7,8)] => 0
[1,1,1,1,0,0,0,0] => [1,1,1,0,0,0,1,0] => [1,1,0,1,1,0,0,0] => [(1,8),(2,3),(4,7),(5,6)] => 0
[1,0,1,0,1,0,1,0,1,0] => [1,1,1,1,1,0,0,0,0,0] => [1,1,1,1,0,1,0,0,0,0] => [(1,10),(2,9),(3,8),(4,5),(6,7)] => 0
[1,0,1,0,1,0,1,1,0,0] => [1,1,1,1,0,1,0,0,0,0] => [1,1,1,0,1,0,1,0,0,0] => [(1,10),(2,9),(3,4),(5,6),(7,8)] => 0
[1,0,1,0,1,1,0,0,1,0] => [1,1,1,0,1,0,1,0,0,0] => [1,1,0,1,0,1,0,1,0,0] => [(1,10),(2,3),(4,5),(6,7),(8,9)] => 0
[1,0,1,0,1,1,0,1,0,0] => [1,1,1,0,1,1,0,0,0,0] => [1,1,0,1,1,0,1,0,0,0] => [(1,10),(2,3),(4,9),(5,6),(7,8)] => 0
[1,0,1,0,1,1,1,0,0,0] => [1,1,1,1,0,0,1,0,0,0] => [1,1,1,0,1,0,0,1,0,0] => [(1,10),(2,7),(3,4),(5,6),(8,9)] => 0
[1,0,1,1,0,0,1,0,1,0] => [1,1,0,1,1,0,0,1,0,0] => [1,0,1,1,0,1,0,0,1,0] => [(1,2),(3,8),(4,5),(6,7),(9,10)] => 0
[1,0,1,1,0,0,1,1,0,0] => [1,1,0,1,0,1,0,1,0,0] => [1,0,1,0,1,0,1,0,1,0] => [(1,2),(3,4),(5,6),(7,8),(9,10)] => 0
[1,0,1,1,0,1,0,0,1,0] => [1,1,0,1,1,0,1,0,0,0] => [1,0,1,1,0,1,0,1,0,0] => [(1,2),(3,10),(4,5),(6,7),(8,9)] => 0
[1,0,1,1,0,1,0,1,0,0] => [1,1,0,1,1,1,0,0,0,0] => [1,0,1,1,1,0,1,0,0,0] => [(1,2),(3,10),(4,9),(5,6),(7,8)] => 0
[1,0,1,1,0,1,1,0,0,0] => [1,1,0,1,0,1,1,0,0,0] => [1,0,1,0,1,1,0,1,0,0] => [(1,2),(3,4),(5,10),(6,7),(8,9)] => 0
[1,0,1,1,1,0,0,0,1,0] => [1,1,1,0,1,0,0,1,0,0] => [1,1,0,1,0,1,0,0,1,0] => [(1,8),(2,3),(4,5),(6,7),(9,10)] => 0
[1,0,1,1,1,0,0,1,0,0] => [1,1,1,0,0,1,0,1,0,0] => [1,1,0,1,0,0,1,0,1,0] => [(1,6),(2,3),(4,5),(7,8),(9,10)] => 0
[1,0,1,1,1,0,1,0,0,0] => [1,1,1,0,0,1,1,0,0,0] => [1,1,0,1,1,0,0,1,0,0] => [(1,10),(2,3),(4,7),(5,6),(8,9)] => 0
[1,0,1,1,1,1,0,0,0,0] => [1,1,1,1,0,0,0,1,0,0] => [1,1,1,0,1,0,0,0,1,0] => [(1,8),(2,7),(3,4),(5,6),(9,10)] => 0
[1,1,0,0,1,0,1,0,1,0] => [1,0,1,1,1,0,0,0,1,0] => [1,1,1,0,0,1,1,0,0,0] => [(1,10),(2,5),(3,4),(6,9),(7,8)] => 0
[1,1,0,0,1,0,1,1,0,0] => [1,0,1,1,0,1,0,0,1,0] => [1,1,0,0,1,0,1,1,0,0] => [(1,4),(2,3),(5,6),(7,10),(8,9)] => 0
[1,1,0,0,1,1,0,0,1,0] => [1,0,1,0,1,0,1,0,1,0] => [1,1,1,1,1,0,0,0,0,0] => [(1,10),(2,9),(3,8),(4,7),(5,6)] => 0
[1,1,0,0,1,1,0,1,0,0] => [1,0,1,0,1,1,0,0,1,0] => [1,1,1,0,0,0,1,1,0,0] => [(1,6),(2,5),(3,4),(7,10),(8,9)] => 0
[1,1,0,0,1,1,1,0,0,0] => [1,0,1,1,0,0,1,0,1,0] => [1,1,0,0,1,1,1,0,0,0] => [(1,4),(2,3),(5,10),(6,9),(7,8)] => 0
[1,1,0,1,0,0,1,0,1,0] => [1,0,1,1,1,0,0,1,0,0] => [1,1,1,0,0,1,0,0,1,0] => [(1,8),(2,5),(3,4),(6,7),(9,10)] => 0
[1,1,0,1,0,0,1,1,0,0] => [1,0,1,1,0,1,0,1,0,0] => [1,1,0,0,1,0,1,0,1,0] => [(1,4),(2,3),(5,6),(7,8),(9,10)] => 0
[1,1,0,1,0,1,0,0,1,0] => [1,0,1,1,1,0,1,0,0,0] => [1,1,1,0,0,1,0,1,0,0] => [(1,10),(2,5),(3,4),(6,7),(8,9)] => 0
[1,1,0,1,0,1,0,1,0,0] => [1,0,1,1,1,1,0,0,0,0] => [1,1,1,1,0,0,1,0,0,0] => [(1,10),(2,9),(3,6),(4,5),(7,8)] => 0
[1,1,0,1,0,1,1,0,0,0] => [1,0,1,1,0,1,1,0,0,0] => [1,1,0,0,1,1,0,1,0,0] => [(1,4),(2,3),(5,10),(6,7),(8,9)] => 0
[1,1,0,1,1,0,0,0,1,0] => [1,0,1,0,1,0,1,1,0,0] => [1,1,1,1,0,0,0,0,1,0] => [(1,8),(2,7),(3,6),(4,5),(9,10)] => 0
[1,1,0,1,1,0,0,1,0,0] => [1,0,1,0,1,1,0,1,0,0] => [1,1,1,0,0,0,1,0,1,0] => [(1,6),(2,5),(3,4),(7,8),(9,10)] => 0
[1,1,0,1,1,0,1,0,0,0] => [1,0,1,0,1,1,1,0,0,0] => [1,1,1,1,0,0,0,1,0,0] => [(1,10),(2,7),(3,6),(4,5),(8,9)] => 0
[1,1,0,1,1,1,0,0,0,0] => [1,0,1,1,0,0,1,1,0,0] => [1,1,0,0,1,1,0,0,1,0] => [(1,4),(2,3),(5,8),(6,7),(9,10)] => 0
[1,1,1,0,0,0,1,0,1,0] => [1,1,0,1,1,0,0,0,1,0] => [1,0,1,1,0,1,1,0,0,0] => [(1,2),(3,10),(4,5),(6,9),(7,8)] => 0
[1,1,1,0,0,0,1,1,0,0] => [1,1,0,1,0,1,0,0,1,0] => [1,0,1,0,1,0,1,1,0,0] => [(1,2),(3,4),(5,6),(7,10),(8,9)] => 0
[1,1,1,0,0,1,0,0,1,0] => [1,1,0,0,1,0,1,0,1,0] => [1,0,1,1,1,1,0,0,0,0] => [(1,2),(3,10),(4,9),(5,8),(6,7)] => 0
[1,1,1,0,0,1,0,1,0,0] => [1,1,0,0,1,1,0,0,1,0] => [1,0,1,1,0,0,1,1,0,0] => [(1,2),(3,6),(4,5),(7,10),(8,9)] => 0
[1,1,1,0,0,1,1,0,0,0] => [1,1,0,1,0,0,1,0,1,0] => [1,0,1,0,1,1,1,0,0,0] => [(1,2),(3,4),(5,10),(6,9),(7,8)] => 0
[1,1,1,0,1,0,0,0,1,0] => [1,1,0,0,1,0,1,1,0,0] => [1,0,1,1,1,0,0,0,1,0] => [(1,2),(3,8),(4,7),(5,6),(9,10)] => 0
[1,1,1,0,1,0,0,1,0,0] => [1,1,0,0,1,1,0,1,0,0] => [1,0,1,1,0,0,1,0,1,0] => [(1,2),(3,6),(4,5),(7,8),(9,10)] => 0
[1,1,1,0,1,0,1,0,0,0] => [1,1,0,0,1,1,1,0,0,0] => [1,0,1,1,1,0,0,1,0,0] => [(1,2),(3,10),(4,7),(5,6),(8,9)] => 0
[1,1,1,0,1,1,0,0,0,0] => [1,1,0,1,0,0,1,1,0,0] => [1,0,1,0,1,1,0,0,1,0] => [(1,2),(3,4),(5,8),(6,7),(9,10)] => 0
[1,1,1,1,0,0,0,0,1,0] => [1,1,1,0,1,0,0,0,1,0] => [1,1,0,1,0,1,1,0,0,0] => [(1,10),(2,3),(4,5),(6,9),(7,8)] => 0
[1,1,1,1,0,0,0,1,0,0] => [1,1,1,0,0,1,0,0,1,0] => [1,1,0,1,0,0,1,1,0,0] => [(1,6),(2,3),(4,5),(7,10),(8,9)] => 0
[1,1,1,1,0,0,1,0,0,0] => [1,1,1,0,0,0,1,0,1,0] => [1,1,0,1,1,1,0,0,0,0] => [(1,10),(2,3),(4,9),(5,8),(6,7)] => 0
[1,1,1,1,0,1,0,0,0,0] => [1,1,1,0,0,0,1,1,0,0] => [1,1,0,1,1,0,0,0,1,0] => [(1,8),(2,3),(4,7),(5,6),(9,10)] => 0
[1,1,1,1,1,0,0,0,0,0] => [1,1,1,1,0,0,0,0,1,0] => [1,1,1,0,1,1,0,0,0,0] => [(1,10),(2,9),(3,4),(5,8),(6,7)] => 0
[1,0,1,1,0,0,1,1,0,0,1,0] => [1,1,0,1,0,1,0,1,0,1,0,0] => [1,0,1,0,1,0,1,0,1,0,1,0] => [(1,2),(3,4),(5,6),(7,8),(9,10),(11,12)] => 0
[1,0,1,1,0,0,1,1,0,1,0,0] => [1,1,0,1,0,1,1,0,0,1,0,0] => [1,0,1,0,1,1,0,1,0,0,1,0] => [(1,2),(3,4),(5,10),(6,7),(8,9),(11,12)] => 0
[1,0,1,1,0,1,1,0,0,0,1,0] => [1,1,0,1,0,1,0,1,1,0,0,0] => [1,0,1,0,1,0,1,1,0,1,0,0] => [(1,2),(3,4),(5,6),(7,12),(8,9),(10,11)] => 0
[1,0,1,1,0,1,1,0,0,1,0,0] => [1,1,0,1,0,1,1,0,1,0,0,0] => [1,0,1,0,1,1,0,1,0,1,0,0] => [(1,2),(3,4),(5,12),(6,7),(8,9),(10,11)] => 0
[1,0,1,1,0,1,1,0,1,0,0,0] => [1,1,0,1,0,1,1,1,0,0,0,0] => [1,0,1,0,1,1,1,0,1,0,0,0] => [(1,2),(3,4),(5,12),(6,11),(7,8),(9,10)] => 0
[1,1,1,0,0,0,1,1,0,0,1,0] => [1,1,0,1,0,1,0,1,0,0,1,0] => [1,0,1,0,1,0,1,0,1,1,0,0] => [(1,2),(3,4),(5,6),(7,8),(9,12),(10,11)] => 0
[1,1,1,0,0,0,1,1,0,1,0,0] => [1,1,0,1,0,1,1,0,0,0,1,0] => [1,0,1,0,1,1,0,1,1,0,0,0] => [(1,2),(3,4),(5,12),(6,7),(8,11),(9,10)] => 0
[1,1,1,0,0,1,1,0,0,0,1,0] => [1,1,0,1,0,1,0,0,1,0,1,0] => [1,0,1,0,1,0,1,1,1,0,0,0] => [(1,2),(3,4),(5,6),(7,12),(8,11),(9,10)] => 0
[1,1,1,0,0,1,1,0,0,1,0,0] => [1,1,0,1,0,0,1,0,1,0,1,0] => [1,0,1,0,1,1,1,1,0,0,0,0] => [(1,2),(3,4),(5,12),(6,11),(7,10),(8,9)] => 0
[1,1,1,0,0,1,1,0,1,0,0,0] => [1,1,0,1,0,0,1,1,0,0,1,0] => [1,0,1,0,1,1,0,0,1,1,0,0] => [(1,2),(3,4),(5,8),(6,7),(9,12),(10,11)] => 0
[1,1,1,0,1,1,0,0,0,0,1,0] => [1,1,0,1,0,1,0,0,1,1,0,0] => [1,0,1,0,1,0,1,1,0,0,1,0] => [(1,2),(3,4),(5,6),(7,10),(8,9),(11,12)] => 0
[1,1,1,0,1,1,0,0,0,1,0,0] => [1,1,0,1,0,0,1,0,1,1,0,0] => [1,0,1,0,1,1,1,0,0,0,1,0] => [(1,2),(3,4),(5,10),(6,9),(7,8),(11,12)] => 0
[1,1,1,0,1,1,0,0,1,0,0,0] => [1,1,0,1,0,0,1,1,0,1,0,0] => [1,0,1,0,1,1,0,0,1,0,1,0] => [(1,2),(3,4),(5,8),(6,7),(9,10),(11,12)] => 0
[1,1,1,0,1,1,0,1,0,0,0,0] => [1,1,0,1,0,0,1,1,1,0,0,0] => [1,0,1,0,1,1,1,0,0,1,0,0] => [(1,2),(3,4),(5,12),(6,9),(7,8),(10,11)] => 0
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
Description
The number of flips required to make a perfect matching noncrossing.
A crossing in a perfect matching is a pair of arcs $\{a,b\}$ and $\{c,d\}$ such that $a < c < b < d$. Replacing any such pair by either $\{a,c\}$ and $\{b,d\}$ or by $\{a,d\}$, $\{b,c\}$ produces a perfect matching with fewer crossings.
This statistic is the minimal number of such flips required to turn a given matching into a noncrossing matching.
A crossing in a perfect matching is a pair of arcs $\{a,b\}$ and $\{c,d\}$ such that $a < c < b < d$. Replacing any such pair by either $\{a,c\}$ and $\{b,d\}$ or by $\{a,d\}$, $\{b,c\}$ produces a perfect matching with fewer crossings.
This statistic is the minimal number of such flips required to turn a given matching into a noncrossing matching.
Map
Knuth-Krattenthaler
Description
The map that sends the Dyck path to a 321-avoiding permutation, then applies the Robinson-Schensted correspondence and finally interprets the first row of the insertion tableau and the second row of the recording tableau as up steps.
Interpreting a pair of two-row standard tableaux of the same shape as a Dyck path is explained by Knuth in [1, pp. 60].
Krattenthaler's bijection between Dyck paths and $321$-avoiding permutations used is Mp00119to 321-avoiding permutation (Krattenthaler), see [2].
This is the inverse of the map Mp00127left-to-right-maxima to Dyck path that interprets the left-to-right maxima of the permutation obtained from Mp00024to 321-avoiding permutation as a Dyck path.
Interpreting a pair of two-row standard tableaux of the same shape as a Dyck path is explained by Knuth in [1, pp. 60].
Krattenthaler's bijection between Dyck paths and $321$-avoiding permutations used is Mp00119to 321-avoiding permutation (Krattenthaler), see [2].
This is the inverse of the map Mp00127left-to-right-maxima to Dyck path that interprets the left-to-right maxima of the permutation obtained from Mp00024to 321-avoiding permutation as a Dyck path.
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.
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
peaks-to-valleys
Description
Return the path that has a valley wherever the original path has a peak of height at least one.
More precisely, the height of a valley in the image is the height of the corresponding peak minus $2$.
This is also (the inverse of) rowmotion on Dyck paths regarded as order ideals in the triangular poset.
More precisely, the height of a valley in the image is the height of the corresponding peak minus $2$.
This is also (the inverse of) rowmotion on Dyck paths regarded as order ideals in the triangular poset.
searching the database
Sorry, this statistic was not found in the database
or
add this statistic to the database – it's very simple and we need your support!