Identifier
-
Mp00031:
Dyck paths
—to 312-avoiding permutation⟶
Permutations
Mp00257: Permutations —Alexandersson Kebede⟶ Permutations
Mp00067: Permutations —Foata bijection⟶ Permutations
St000308: Permutations ⟶ ℤ
Values
[1,0] => [1] => [1] => [1] => 1
[1,0,1,0] => [1,2] => [1,2] => [1,2] => 2
[1,1,0,0] => [2,1] => [2,1] => [2,1] => 1
[1,0,1,0,1,0] => [1,2,3] => [1,2,3] => [1,2,3] => 3
[1,0,1,1,0,0] => [1,3,2] => [3,1,2] => [1,3,2] => 2
[1,1,0,0,1,0] => [2,1,3] => [2,1,3] => [2,1,3] => 2
[1,1,0,1,0,0] => [2,3,1] => [3,2,1] => [3,2,1] => 1
[1,1,1,0,0,0] => [3,2,1] => [2,3,1] => [2,3,1] => 2
[1,0,1,0,1,0,1,0] => [1,2,3,4] => [1,2,3,4] => [1,2,3,4] => 4
[1,0,1,0,1,1,0,0] => [1,2,4,3] => [1,2,4,3] => [4,1,2,3] => 3
[1,0,1,1,0,0,1,0] => [1,3,2,4] => [3,1,2,4] => [1,3,2,4] => 3
[1,0,1,1,0,1,0,0] => [1,3,4,2] => [3,1,4,2] => [3,4,1,2] => 2
[1,0,1,1,1,0,0,0] => [1,4,3,2] => [4,1,3,2] => [4,1,3,2] => 2
[1,1,0,0,1,0,1,0] => [2,1,3,4] => [2,1,3,4] => [2,1,3,4] => 3
[1,1,0,0,1,1,0,0] => [2,1,4,3] => [2,1,4,3] => [4,2,1,3] => 2
[1,1,0,1,0,0,1,0] => [2,3,1,4] => [3,2,1,4] => [3,2,1,4] => 2
[1,1,0,1,0,1,0,0] => [2,3,4,1] => [3,2,4,1] => [3,2,4,1] => 2
[1,1,0,1,1,0,0,0] => [2,4,3,1] => [4,2,3,1] => [2,4,3,1] => 2
[1,1,1,0,0,0,1,0] => [3,2,1,4] => [2,3,1,4] => [2,3,1,4] => 2
[1,1,1,0,0,1,0,0] => [3,2,4,1] => [2,3,4,1] => [2,3,4,1] => 3
[1,1,1,0,1,0,0,0] => [3,4,2,1] => [4,3,2,1] => [4,3,2,1] => 1
[1,1,1,1,0,0,0,0] => [4,3,2,1] => [3,4,2,1] => [3,4,2,1] => 2
[1,0,1,0,1,0,1,0,1,0] => [1,2,3,4,5] => [1,2,3,4,5] => [1,2,3,4,5] => 5
[1,0,1,0,1,0,1,1,0,0] => [1,2,3,5,4] => [1,2,5,3,4] => [1,5,2,3,4] => 4
[1,0,1,0,1,1,0,0,1,0] => [1,2,4,3,5] => [1,2,4,3,5] => [4,1,2,3,5] => 4
[1,0,1,0,1,1,0,1,0,0] => [1,2,4,5,3] => [1,2,5,4,3] => [5,4,1,2,3] => 3
[1,0,1,0,1,1,1,0,0,0] => [1,2,5,4,3] => [1,2,4,5,3] => [4,1,2,5,3] => 3
[1,0,1,1,0,0,1,0,1,0] => [1,3,2,4,5] => [3,1,2,4,5] => [1,3,2,4,5] => 4
[1,0,1,1,0,0,1,1,0,0] => [1,3,2,5,4] => [3,1,2,5,4] => [5,1,3,2,4] => 3
[1,0,1,1,0,1,0,0,1,0] => [1,3,4,2,5] => [3,1,4,2,5] => [3,4,1,2,5] => 3
[1,0,1,1,0,1,0,1,0,0] => [1,3,4,5,2] => [3,1,4,5,2] => [3,4,1,5,2] => 2
[1,0,1,1,0,1,1,0,0,0] => [1,3,5,4,2] => [3,1,5,4,2] => [5,3,4,1,2] => 2
[1,0,1,1,1,0,0,0,1,0] => [1,4,3,2,5] => [4,1,3,2,5] => [4,1,3,2,5] => 3
[1,0,1,1,1,0,0,1,0,0] => [1,4,3,5,2] => [4,1,3,5,2] => [4,1,3,5,2] => 3
[1,0,1,1,1,0,1,0,0,0] => [1,4,5,3,2] => [4,1,5,3,2] => [4,5,3,1,2] => 2
[1,0,1,1,1,1,0,0,0,0] => [1,5,4,3,2] => [5,1,4,3,2] => [5,4,1,3,2] => 2
[1,1,0,0,1,0,1,0,1,0] => [2,1,3,4,5] => [2,1,3,4,5] => [2,1,3,4,5] => 4
[1,1,0,0,1,0,1,1,0,0] => [2,1,3,5,4] => [2,1,5,3,4] => [2,5,1,3,4] => 3
[1,1,0,0,1,1,0,0,1,0] => [2,1,4,3,5] => [2,1,4,3,5] => [4,2,1,3,5] => 3
[1,1,0,0,1,1,0,1,0,0] => [2,1,4,5,3] => [2,1,5,4,3] => [5,4,2,1,3] => 2
[1,1,0,0,1,1,1,0,0,0] => [2,1,5,4,3] => [2,1,4,5,3] => [4,2,1,5,3] => 2
[1,1,0,1,0,0,1,0,1,0] => [2,3,1,4,5] => [3,2,1,4,5] => [3,2,1,4,5] => 3
[1,1,0,1,0,0,1,1,0,0] => [2,3,1,5,4] => [3,2,1,5,4] => [5,3,2,1,4] => 2
[1,1,0,1,0,1,0,0,1,0] => [2,3,4,1,5] => [3,2,4,1,5] => [3,2,4,1,5] => 2
[1,1,0,1,0,1,0,1,0,0] => [2,3,4,5,1] => [3,2,4,5,1] => [3,2,4,5,1] => 3
[1,1,0,1,0,1,1,0,0,0] => [2,3,5,4,1] => [3,2,5,4,1] => [5,3,2,4,1] => 2
[1,1,0,1,1,0,0,0,1,0] => [2,4,3,1,5] => [4,2,3,1,5] => [2,4,3,1,5] => 2
[1,1,0,1,1,0,0,1,0,0] => [2,4,3,5,1] => [4,2,3,5,1] => [2,4,3,5,1] => 3
[1,1,0,1,1,0,1,0,0,0] => [2,4,5,3,1] => [4,2,5,3,1] => [4,5,2,3,1] => 2
[1,1,0,1,1,1,0,0,0,0] => [2,5,4,3,1] => [5,2,4,3,1] => [5,2,4,3,1] => 2
[1,1,1,0,0,0,1,0,1,0] => [3,2,1,4,5] => [2,3,1,4,5] => [2,3,1,4,5] => 3
[1,1,1,0,0,0,1,1,0,0] => [3,2,1,5,4] => [2,3,1,5,4] => [5,2,3,1,4] => 2
[1,1,1,0,0,1,0,0,1,0] => [3,2,4,1,5] => [2,3,4,1,5] => [2,3,4,1,5] => 3
[1,1,1,0,0,1,0,1,0,0] => [3,2,4,5,1] => [2,3,4,5,1] => [2,3,4,5,1] => 4
[1,1,1,0,0,1,1,0,0,0] => [3,2,5,4,1] => [2,3,5,4,1] => [5,2,3,4,1] => 3
[1,1,1,0,1,0,0,0,1,0] => [3,4,2,1,5] => [4,3,2,1,5] => [4,3,2,1,5] => 2
[1,1,1,0,1,0,0,1,0,0] => [3,4,2,5,1] => [4,3,2,5,1] => [4,3,2,5,1] => 2
[1,1,1,0,1,0,1,0,0,0] => [3,4,5,2,1] => [4,3,5,2,1] => [4,3,5,2,1] => 2
[1,1,1,0,1,1,0,0,0,0] => [3,5,4,2,1] => [5,3,4,2,1] => [3,5,4,2,1] => 2
[1,1,1,1,0,0,0,0,1,0] => [4,3,2,1,5] => [3,4,2,1,5] => [3,4,2,1,5] => 2
[1,1,1,1,0,0,0,1,0,0] => [4,3,2,5,1] => [3,4,2,5,1] => [3,4,2,5,1] => 2
[1,1,1,1,0,0,1,0,0,0] => [4,3,5,2,1] => [3,4,5,2,1] => [3,4,5,2,1] => 3
[1,1,1,1,0,1,0,0,0,0] => [4,5,3,2,1] => [5,4,3,2,1] => [5,4,3,2,1] => 1
[1,1,1,1,1,0,0,0,0,0] => [5,4,3,2,1] => [4,5,3,2,1] => [4,5,3,2,1] => 2
[1,0,1,0,1,0,1,0,1,0,1,0] => [1,2,3,4,5,6] => [1,2,3,4,5,6] => [1,2,3,4,5,6] => 6
[1,0,1,0,1,0,1,0,1,1,0,0] => [1,2,3,4,6,5] => [1,2,3,4,6,5] => [6,1,2,3,4,5] => 5
[1,0,1,0,1,0,1,1,0,0,1,0] => [1,2,3,5,4,6] => [1,2,5,3,4,6] => [1,5,2,3,4,6] => 5
[1,0,1,0,1,0,1,1,0,1,0,0] => [1,2,3,5,6,4] => [1,2,5,3,6,4] => [5,6,1,2,3,4] => 4
[1,0,1,0,1,0,1,1,1,0,0,0] => [1,2,3,6,5,4] => [1,2,6,3,5,4] => [6,1,5,2,3,4] => 4
[1,0,1,0,1,1,0,0,1,0,1,0] => [1,2,4,3,5,6] => [1,2,4,3,5,6] => [4,1,2,3,5,6] => 5
[1,0,1,0,1,1,0,0,1,1,0,0] => [1,2,4,3,6,5] => [1,2,4,3,6,5] => [6,4,1,2,3,5] => 4
[1,0,1,0,1,1,0,1,0,0,1,0] => [1,2,4,5,3,6] => [1,2,5,4,3,6] => [5,4,1,2,3,6] => 4
[1,0,1,0,1,1,0,1,0,1,0,0] => [1,2,4,5,6,3] => [1,2,5,4,6,3] => [5,4,1,2,6,3] => 3
[1,0,1,0,1,1,0,1,1,0,0,0] => [1,2,4,6,5,3] => [1,2,6,4,5,3] => [6,1,4,2,5,3] => 3
[1,0,1,0,1,1,1,0,0,0,1,0] => [1,2,5,4,3,6] => [1,2,4,5,3,6] => [4,1,2,5,3,6] => 4
[1,0,1,0,1,1,1,0,0,1,0,0] => [1,2,5,4,6,3] => [1,2,4,5,6,3] => [4,1,2,5,6,3] => 4
[1,0,1,0,1,1,1,0,1,0,0,0] => [1,2,5,6,4,3] => [1,2,6,5,4,3] => [6,5,4,1,2,3] => 3
[1,0,1,0,1,1,1,1,0,0,0,0] => [1,2,6,5,4,3] => [1,2,5,6,4,3] => [5,6,1,2,4,3] => 3
[1,0,1,1,0,0,1,0,1,0,1,0] => [1,3,2,4,5,6] => [3,1,2,4,5,6] => [1,3,2,4,5,6] => 5
[1,0,1,1,0,0,1,0,1,1,0,0] => [1,3,2,4,6,5] => [3,1,2,4,6,5] => [6,1,3,2,4,5] => 4
[1,0,1,1,0,0,1,1,0,0,1,0] => [1,3,2,5,4,6] => [3,1,2,5,4,6] => [5,1,3,2,4,6] => 4
[1,0,1,1,0,0,1,1,0,1,0,0] => [1,3,2,5,6,4] => [3,1,2,5,6,4] => [5,1,3,2,6,4] => 3
[1,0,1,1,0,0,1,1,1,0,0,0] => [1,3,2,6,5,4] => [3,1,2,6,5,4] => [6,5,1,3,2,4] => 3
[1,0,1,1,0,1,0,0,1,0,1,0] => [1,3,4,2,5,6] => [3,1,4,2,5,6] => [3,4,1,2,5,6] => 4
[1,0,1,1,0,1,0,0,1,1,0,0] => [1,3,4,2,6,5] => [3,1,4,2,6,5] => [6,3,4,1,2,5] => 3
[1,0,1,1,0,1,0,1,0,0,1,0] => [1,3,4,5,2,6] => [3,1,4,5,2,6] => [3,4,1,5,2,6] => 3
[1,0,1,1,0,1,0,1,0,1,0,0] => [1,3,4,5,6,2] => [3,1,4,5,6,2] => [3,4,1,5,6,2] => 3
[1,0,1,1,0,1,0,1,1,0,0,0] => [1,3,4,6,5,2] => [3,1,4,6,5,2] => [6,3,4,1,5,2] => 2
[1,0,1,1,0,1,1,0,0,0,1,0] => [1,3,5,4,2,6] => [3,1,5,4,2,6] => [5,3,4,1,2,6] => 3
[1,0,1,1,0,1,1,0,0,1,0,0] => [1,3,5,4,6,2] => [3,1,5,4,6,2] => [5,3,4,1,6,2] => 2
[1,0,1,1,0,1,1,0,1,0,0,0] => [1,3,5,6,4,2] => [3,1,5,6,4,2] => [5,3,6,1,4,2] => 2
[1,0,1,1,0,1,1,1,0,0,0,0] => [1,3,6,5,4,2] => [3,1,6,5,4,2] => [6,5,3,4,1,2] => 2
[1,0,1,1,1,0,0,0,1,0,1,0] => [1,4,3,2,5,6] => [4,1,3,2,5,6] => [4,1,3,2,5,6] => 4
[1,0,1,1,1,0,0,0,1,1,0,0] => [1,4,3,2,6,5] => [4,1,3,2,6,5] => [6,4,1,3,2,5] => 3
[1,0,1,1,1,0,0,1,0,0,1,0] => [1,4,3,5,2,6] => [4,1,3,5,2,6] => [4,1,3,5,2,6] => 3
[1,0,1,1,1,0,0,1,0,1,0,0] => [1,4,3,5,6,2] => [4,1,3,5,6,2] => [4,1,3,5,6,2] => 4
[1,0,1,1,1,0,0,1,1,0,0,0] => [1,4,3,6,5,2] => [4,1,3,6,5,2] => [6,4,1,3,5,2] => 3
[1,0,1,1,1,0,1,0,0,0,1,0] => [1,4,5,3,2,6] => [4,1,5,3,2,6] => [4,5,3,1,2,6] => 3
[1,0,1,1,1,0,1,0,0,1,0,0] => [1,4,5,3,6,2] => [4,1,5,3,6,2] => [4,5,3,1,6,2] => 2
[1,0,1,1,1,0,1,0,1,0,0,0] => [1,4,5,6,3,2] => [4,1,5,6,3,2] => [4,5,6,1,3,2] => 3
[1,0,1,1,1,0,1,1,0,0,0,0] => [1,4,6,5,3,2] => [4,1,6,5,3,2] => [6,4,5,3,1,2] => 2
>>> Load all 359 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
Description
The height of the tree associated to a permutation.
A permutation can be mapped to a rooted tree with vertices {0,1,2,…,n} and root 0 in the following way. Entries of the permutations are inserted one after the other, each child is larger than its parent and the children are in strict order from left to right. Details of the construction are found in [1].
The statistic is given by the height of this tree.
See also St000325The width of the tree associated to a permutation. for the width of this tree.
A permutation can be mapped to a rooted tree with vertices {0,1,2,…,n} and root 0 in the following way. Entries of the permutations are inserted one after the other, each child is larger than its parent and the children are in strict order from left to right. Details of the construction are found in [1].
The statistic is given by the height of this tree.
See also St000325The width of the tree associated to a permutation. for the width of this tree.
Map
to 312-avoiding permutation
Description
Map
Foata bijection
Description
Sends a permutation to its image under the Foata bijection.
The Foata bijection ϕ is a bijection on the set of words with no two equal letters. It can be defined by induction on the size of the word:
Given a word w1w2...wn, compute the image inductively by starting with ϕ(w1)=w1.
At the i-th step, if ϕ(w1w2...wi)=v1v2...vi, define ϕ(w1w2...wiwi+1) by placing wi+1 on the end of the word v1v2...vi and breaking the word up into blocks as follows.
To compute ϕ([1,4,2,5,3]), the sequence of words is
This bijection sends the major index (St000004The major index of a permutation.) to the number of inversions (St000018The number of inversions of a permutation.).
The Foata bijection ϕ is a bijection on the set of words with no two equal letters. It can be defined by induction on the size of the word:
Given a word w1w2...wn, compute the image inductively by starting with ϕ(w1)=w1.
At the i-th step, if ϕ(w1w2...wi)=v1v2...vi, define ϕ(w1w2...wiwi+1) by placing wi+1 on the end of the word v1v2...vi and breaking the word up into blocks as follows.
- If wi+1≥vi, place a vertical line to the right of each vk for which wi+1≥vk.
- If wi+1<vi, place a vertical line to the right of each vk for which wi+1<vk.
To compute ϕ([1,4,2,5,3]), the sequence of words is
- 1
- |1|4→14
- |14|2→412
- |4|1|2|5→4125
- |4|125|3→45123.
This bijection sends the major index (St000004The major index of a permutation.) to the number of inversions (St000018The number of inversions of a permutation.).
Map
Alexandersson Kebede
Description
Sends a permutation to a permutation and it preserves the set of right-to-left minima.
Take a permutation π of length n. The mapping looks for a smallest odd integer i∈[n−1] such that swapping the entries π(i) and π(i+1) preserves the set of right-to-left minima. Otherwise, π will be a fixed element of the mapping. Note that the map changes the sign of all non-fixed elements.
There are exactly \binom{\lfloor n/2 \rfloor}{k-\lceil n/2 \rceil} elements in S_n fixed under this map, with exactly k right-to-left minima, see Lemma 35 in [1].
Take a permutation π of length n. The mapping looks for a smallest odd integer i∈[n−1] such that swapping the entries π(i) and π(i+1) preserves the set of right-to-left minima. Otherwise, π will be a fixed element of the mapping. Note that the map changes the sign of all non-fixed elements.
There are exactly \binom{\lfloor n/2 \rfloor}{k-\lceil n/2 \rceil} elements in S_n fixed under this map, with exactly k right-to-left minima, see Lemma 35 in [1].
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!