Identifier
-
Mp00050:
Ordered trees
—to binary tree: right brother = right child⟶
Binary trees
Mp00017: Binary trees —to 312-avoiding permutation⟶ Permutations
Mp00062: Permutations —Lehmer-code to major-code bijection⟶ Permutations
St000662: Permutations ⟶ ℤ
Values
[[]] => [.,.] => [1] => [1] => 0
[[],[]] => [.,[.,.]] => [2,1] => [2,1] => 1
[[[]]] => [[.,.],.] => [1,2] => [1,2] => 0
[[],[],[]] => [.,[.,[.,.]]] => [3,2,1] => [3,2,1] => 2
[[],[[]]] => [.,[[.,.],.]] => [2,3,1] => [1,3,2] => 1
[[[]],[]] => [[.,.],[.,.]] => [1,3,2] => [3,1,2] => 1
[[[],[]]] => [[.,[.,.]],.] => [2,1,3] => [2,1,3] => 1
[[[[]]]] => [[[.,.],.],.] => [1,2,3] => [1,2,3] => 0
[[],[],[],[]] => [.,[.,[.,[.,.]]]] => [4,3,2,1] => [4,3,2,1] => 3
[[],[],[[]]] => [.,[.,[[.,.],.]]] => [3,4,2,1] => [1,4,3,2] => 2
[[],[[]],[]] => [.,[[.,.],[.,.]]] => [2,4,3,1] => [4,1,3,2] => 2
[[],[[],[]]] => [.,[[.,[.,.]],.]] => [3,2,4,1] => [2,1,4,3] => 1
[[],[[[]]]] => [.,[[[.,.],.],.]] => [2,3,4,1] => [1,2,4,3] => 1
[[[]],[],[]] => [[.,.],[.,[.,.]]] => [1,4,3,2] => [4,3,1,2] => 2
[[[]],[[]]] => [[.,.],[[.,.],.]] => [1,3,4,2] => [2,4,1,3] => 1
[[[],[]],[]] => [[.,[.,.]],[.,.]] => [2,1,4,3] => [1,4,2,3] => 1
[[[[]]],[]] => [[[.,.],.],[.,.]] => [1,2,4,3] => [4,1,2,3] => 1
[[[],[],[]]] => [[.,[.,[.,.]]],.] => [3,2,1,4] => [3,2,1,4] => 2
[[[],[[]]]] => [[.,[[.,.],.]],.] => [2,3,1,4] => [1,3,2,4] => 1
[[[[]],[]]] => [[[.,.],[.,.]],.] => [1,3,2,4] => [3,1,2,4] => 1
[[[[],[]]]] => [[[.,[.,.]],.],.] => [2,1,3,4] => [2,1,3,4] => 1
[[[[[]]]]] => [[[[.,.],.],.],.] => [1,2,3,4] => [1,2,3,4] => 0
[[],[],[],[],[]] => [.,[.,[.,[.,[.,.]]]]] => [5,4,3,2,1] => [5,4,3,2,1] => 4
[[],[],[],[[]]] => [.,[.,[.,[[.,.],.]]]] => [4,5,3,2,1] => [1,5,4,3,2] => 3
[[],[],[[]],[]] => [.,[.,[[.,.],[.,.]]]] => [3,5,4,2,1] => [5,1,4,3,2] => 3
[[],[],[[],[]]] => [.,[.,[[.,[.,.]],.]]] => [4,3,5,2,1] => [2,1,5,4,3] => 2
[[],[],[[[]]]] => [.,[.,[[[.,.],.],.]]] => [3,4,5,2,1] => [1,2,5,4,3] => 2
[[],[[]],[],[]] => [.,[[.,.],[.,[.,.]]]] => [2,5,4,3,1] => [5,4,1,3,2] => 3
[[],[[]],[[]]] => [.,[[.,.],[[.,.],.]]] => [2,4,5,3,1] => [2,5,1,4,3] => 2
[[],[[],[]],[]] => [.,[[.,[.,.]],[.,.]]] => [3,2,5,4,1] => [1,5,2,4,3] => 2
[[],[[[]]],[]] => [.,[[[.,.],.],[.,.]]] => [2,3,5,4,1] => [5,1,2,4,3] => 2
[[],[[],[],[]]] => [.,[[.,[.,[.,.]]],.]] => [4,3,2,5,1] => [3,2,1,5,4] => 2
[[],[[],[[]]]] => [.,[[.,[[.,.],.]],.]] => [3,4,2,5,1] => [1,3,2,5,4] => 1
[[],[[[]],[]]] => [.,[[[.,.],[.,.]],.]] => [2,4,3,5,1] => [3,1,2,5,4] => 2
[[],[[[],[]]]] => [.,[[[.,[.,.]],.],.]] => [3,2,4,5,1] => [2,1,3,5,4] => 1
[[],[[[[]]]]] => [.,[[[[.,.],.],.],.]] => [2,3,4,5,1] => [1,2,3,5,4] => 1
[[[]],[],[],[]] => [[.,.],[.,[.,[.,.]]]] => [1,5,4,3,2] => [5,4,3,1,2] => 3
[[[]],[],[[]]] => [[.,.],[.,[[.,.],.]]] => [1,4,5,3,2] => [2,5,4,1,3] => 2
[[[]],[[]],[]] => [[.,.],[[.,.],[.,.]]] => [1,3,5,4,2] => [5,2,4,1,3] => 2
[[[]],[[],[]]] => [[.,.],[[.,[.,.]],.]] => [1,4,3,5,2] => [3,2,5,1,4] => 2
[[[]],[[[]]]] => [[.,.],[[[.,.],.],.]] => [1,3,4,5,2] => [2,3,5,1,4] => 1
[[[],[]],[],[]] => [[.,[.,.]],[.,[.,.]]] => [2,1,5,4,3] => [5,1,4,2,3] => 2
[[[[]]],[],[]] => [[[.,.],.],[.,[.,.]]] => [1,2,5,4,3] => [5,4,1,2,3] => 2
[[[],[]],[[]]] => [[.,[.,.]],[[.,.],.]] => [2,1,4,5,3] => [1,3,5,2,4] => 1
[[[[]]],[[]]] => [[[.,.],.],[[.,.],.]] => [1,2,4,5,3] => [3,5,1,2,4] => 2
[[[],[],[]],[]] => [[.,[.,[.,.]]],[.,.]] => [3,2,1,5,4] => [2,1,5,3,4] => 1
[[[],[[]]],[]] => [[.,[[.,.],.]],[.,.]] => [2,3,1,5,4] => [1,2,5,3,4] => 1
[[[[]],[]],[]] => [[[.,.],[.,.]],[.,.]] => [1,3,2,5,4] => [2,5,1,3,4] => 1
[[[[],[]]],[]] => [[[.,[.,.]],.],[.,.]] => [2,1,3,5,4] => [1,5,2,3,4] => 1
[[[[[]]]],[]] => [[[[.,.],.],.],[.,.]] => [1,2,3,5,4] => [5,1,2,3,4] => 1
[[[],[],[],[]]] => [[.,[.,[.,[.,.]]]],.] => [4,3,2,1,5] => [4,3,2,1,5] => 3
[[[],[],[[]]]] => [[.,[.,[[.,.],.]]],.] => [3,4,2,1,5] => [1,4,3,2,5] => 2
[[[],[[]],[]]] => [[.,[[.,.],[.,.]]],.] => [2,4,3,1,5] => [4,1,3,2,5] => 2
[[[],[[],[]]]] => [[.,[[.,[.,.]],.]],.] => [3,2,4,1,5] => [2,1,4,3,5] => 1
[[[],[[[]]]]] => [[.,[[[.,.],.],.]],.] => [2,3,4,1,5] => [1,2,4,3,5] => 1
[[[[]],[],[]]] => [[[.,.],[.,[.,.]]],.] => [1,4,3,2,5] => [4,3,1,2,5] => 2
[[[[]],[[]]]] => [[[.,.],[[.,.],.]],.] => [1,3,4,2,5] => [2,4,1,3,5] => 1
[[[[],[]],[]]] => [[[.,[.,.]],[.,.]],.] => [2,1,4,3,5] => [1,4,2,3,5] => 1
[[[[[]]],[]]] => [[[[.,.],.],[.,.]],.] => [1,2,4,3,5] => [4,1,2,3,5] => 1
[[[[],[],[]]]] => [[[.,[.,[.,.]]],.],.] => [3,2,1,4,5] => [3,2,1,4,5] => 2
[[[[],[[]]]]] => [[[.,[[.,.],.]],.],.] => [2,3,1,4,5] => [1,3,2,4,5] => 1
[[[[[]],[]]]] => [[[[.,.],[.,.]],.],.] => [1,3,2,4,5] => [3,1,2,4,5] => 1
[[[[[],[]]]]] => [[[[.,[.,.]],.],.],.] => [2,1,3,4,5] => [2,1,3,4,5] => 1
[[[[[[]]]]]] => [[[[[.,.],.],.],.],.] => [1,2,3,4,5] => [1,2,3,4,5] => 0
[[],[],[],[],[],[]] => [.,[.,[.,[.,[.,[.,.]]]]]] => [6,5,4,3,2,1] => [6,5,4,3,2,1] => 5
[[],[],[],[],[[]]] => [.,[.,[.,[.,[[.,.],.]]]]] => [5,6,4,3,2,1] => [1,6,5,4,3,2] => 4
[[],[],[],[[]],[]] => [.,[.,[.,[[.,.],[.,.]]]]] => [4,6,5,3,2,1] => [6,1,5,4,3,2] => 4
[[],[],[],[[],[]]] => [.,[.,[.,[[.,[.,.]],.]]]] => [5,4,6,3,2,1] => [2,1,6,5,4,3] => 3
[[],[],[],[[[]]]] => [.,[.,[.,[[[.,.],.],.]]]] => [4,5,6,3,2,1] => [1,2,6,5,4,3] => 3
[[],[],[[]],[],[]] => [.,[.,[[.,.],[.,[.,.]]]]] => [3,6,5,4,2,1] => [6,5,1,4,3,2] => 4
[[],[],[[]],[[]]] => [.,[.,[[.,.],[[.,.],.]]]] => [3,5,6,4,2,1] => [2,6,1,5,4,3] => 3
[[],[],[[],[]],[]] => [.,[.,[[.,[.,.]],[.,.]]]] => [4,3,6,5,2,1] => [1,6,2,5,4,3] => 3
[[],[],[[[]]],[]] => [.,[.,[[[.,.],.],[.,.]]]] => [3,4,6,5,2,1] => [6,1,2,5,4,3] => 3
[[],[],[[],[],[]]] => [.,[.,[[.,[.,[.,.]]],.]]] => [5,4,3,6,2,1] => [3,2,1,6,5,4] => 2
[[],[],[[],[[]]]] => [.,[.,[[.,[[.,.],.]],.]]] => [4,5,3,6,2,1] => [1,3,2,6,5,4] => 2
[[],[],[[[]],[]]] => [.,[.,[[[.,.],[.,.]],.]]] => [3,5,4,6,2,1] => [3,1,2,6,5,4] => 2
[[],[],[[[],[]]]] => [.,[.,[[[.,[.,.]],.],.]]] => [4,3,5,6,2,1] => [2,1,3,6,5,4] => 2
[[],[],[[[[]]]]] => [.,[.,[[[[.,.],.],.],.]]] => [3,4,5,6,2,1] => [1,2,3,6,5,4] => 2
[[],[[]],[],[],[]] => [.,[[.,.],[.,[.,[.,.]]]]] => [2,6,5,4,3,1] => [6,5,4,1,3,2] => 4
[[],[[]],[],[[]]] => [.,[[.,.],[.,[[.,.],.]]]] => [2,5,6,4,3,1] => [2,6,5,1,4,3] => 3
[[],[[]],[[]],[]] => [.,[[.,.],[[.,.],[.,.]]]] => [2,4,6,5,3,1] => [6,2,5,1,4,3] => 3
[[],[[]],[[],[]]] => [.,[[.,.],[[.,[.,.]],.]]] => [2,5,4,6,3,1] => [3,2,6,1,5,4] => 2
[[],[[]],[[[]]]] => [.,[[.,.],[[[.,.],.],.]]] => [2,4,5,6,3,1] => [2,3,6,1,5,4] => 2
[[],[[],[]],[],[]] => [.,[[.,[.,.]],[.,[.,.]]]] => [3,2,6,5,4,1] => [6,1,5,2,4,3] => 3
[[],[[[]]],[],[]] => [.,[[[.,.],.],[.,[.,.]]]] => [2,3,6,5,4,1] => [6,5,1,2,4,3] => 3
[[],[[],[]],[[]]] => [.,[[.,[.,.]],[[.,.],.]]] => [3,2,5,6,4,1] => [1,3,6,2,5,4] => 2
[[],[[[]]],[[]]] => [.,[[[.,.],.],[[.,.],.]]] => [2,3,5,6,4,1] => [3,6,1,2,5,4] => 2
[[],[[],[],[]],[]] => [.,[[.,[.,[.,.]]],[.,.]]] => [4,3,2,6,5,1] => [2,1,6,3,5,4] => 2
[[],[[],[[]]],[]] => [.,[[.,[[.,.],.]],[.,.]]] => [3,4,2,6,5,1] => [1,2,6,3,5,4] => 2
[[],[[[]],[]],[]] => [.,[[[.,.],[.,.]],[.,.]]] => [2,4,3,6,5,1] => [2,6,1,3,5,4] => 2
[[],[[[],[]]],[]] => [.,[[[.,[.,.]],.],[.,.]]] => [3,2,4,6,5,1] => [1,6,2,3,5,4] => 2
[[],[[[[]]]],[]] => [.,[[[[.,.],.],.],[.,.]]] => [2,3,4,6,5,1] => [6,1,2,3,5,4] => 2
[[],[[],[],[],[]]] => [.,[[.,[.,[.,[.,.]]]],.]] => [5,4,3,2,6,1] => [4,3,2,1,6,5] => 3
[[],[[],[],[[]]]] => [.,[[.,[.,[[.,.],.]]],.]] => [4,5,3,2,6,1] => [1,4,3,2,6,5] => 2
[[],[[],[[]],[]]] => [.,[[.,[[.,.],[.,.]]],.]] => [3,5,4,2,6,1] => [4,1,3,2,6,5] => 2
[[],[[],[[],[]]]] => [.,[[.,[[.,[.,.]],.]],.]] => [4,3,5,2,6,1] => [2,1,4,3,6,5] => 1
[[],[[],[[[]]]]] => [.,[[.,[[[.,.],.],.]],.]] => [3,4,5,2,6,1] => [1,2,4,3,6,5] => 1
[[],[[[]],[],[]]] => [.,[[[.,.],[.,[.,.]]],.]] => [2,5,4,3,6,1] => [4,3,1,2,6,5] => 3
[[],[[[]],[[]]]] => [.,[[[.,.],[[.,.],.]],.]] => [2,4,5,3,6,1] => [2,4,1,3,6,5] => 2
[[],[[[],[]],[]]] => [.,[[[.,[.,.]],[.,.]],.]] => [3,2,5,4,6,1] => [1,4,2,3,6,5] => 2
[[],[[[[]]],[]]] => [.,[[[[.,.],.],[.,.]],.]] => [2,3,5,4,6,1] => [4,1,2,3,6,5] => 2
>>> Load all 407 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 staircase size of the code of a permutation.
The code $c(\pi)$ of a permutation $\pi$ of length $n$ is given by the sequence $(c_1,\ldots,c_{n})$ with $c_i = |\{j > i : \pi(j) < \pi(i)\}|$. This is a bijection between permutations and all sequences $(c_1,\ldots,c_n)$ with $0 \leq c_i \leq n-i$.
The staircase size of the code is the maximal $k$ such that there exists a subsequence $(c_{i_k},\ldots,c_{i_1})$ of $c(\pi)$ with $c_{i_j} \geq j$.
This statistic is mapped through Mp00062Lehmer-code to major-code bijection to the number of descents, showing that together with the number of inversions St000018The number of inversions of a permutation. it is Euler-Mahonian.
The code $c(\pi)$ of a permutation $\pi$ of length $n$ is given by the sequence $(c_1,\ldots,c_{n})$ with $c_i = |\{j > i : \pi(j) < \pi(i)\}|$. This is a bijection between permutations and all sequences $(c_1,\ldots,c_n)$ with $0 \leq c_i \leq n-i$.
The staircase size of the code is the maximal $k$ such that there exists a subsequence $(c_{i_k},\ldots,c_{i_1})$ of $c(\pi)$ with $c_{i_j} \geq j$.
This statistic is mapped through Mp00062Lehmer-code to major-code bijection to the number of descents, showing that together with the number of inversions St000018The number of inversions of a permutation. it is Euler-Mahonian.
Map
Lehmer-code to major-code bijection
Description
Sends a permutation to the unique permutation such that the Lehmer code is sent to the major code.
The Lehmer code encodes the inversions of a permutation and the major code encodes its major index. In particular, the number of inversions of a permutation equals the major index of its image under this map.
* The Lehmer code of a permutation $\sigma$ is given by $L(\sigma) = l_1 \ldots l_n$ with $l_i = \# \{ j > i : \sigma_j < \sigma_i \}$. In particular, $l_i$ is the number of boxes in the $i$-th column of the Rothe diagram. For example, the Lehmer code of $\sigma = [4,3,1,5,2]$ is $32010$. The Lehmer code $L : \mathfrak{S}_n\ \tilde\longrightarrow\ S_n$ is a bijection between permutations of size $n$ and sequences $l_1\ldots l_n \in \mathbf{N}^n$ with $l_i \leq i$.
* The major code $M(\sigma)$ of a permutation $\sigma \in \mathfrak{S}_n$ is a way to encode a permutation as a sequence $m_1 m_2 \ldots m_n$ with $m_i \geq i$. To define $m_i$, let $\operatorname{del}_i(\sigma)$ be the normalized permutation obtained by removing all $\sigma_j < i$ from the one-line notation of $\sigma$. The $i$-th index is then given by
$$m_i = \operatorname{maj}(\operatorname{del}_i(\sigma)) - \operatorname{maj}(\operatorname{del}_{i-1}(\sigma)).$$
For example, the permutation $[9,3,5,7,2,1,4,6,8]$ has major code $[5, 0, 1, 0, 1, 2, 0, 1, 0]$ since
$$\operatorname{maj}([8,2,4,6,1,3,5,7]) = 5, \quad \operatorname{maj}([7,1,3,5,2,4,6]) = 5, \quad \operatorname{maj}([6,2,4,1,3,5]) = 4,$$
$$\operatorname{maj}([5,1,3,2,4]) = 4, \quad \operatorname{maj}([4,2,1,3]) = 3, \quad \operatorname{maj}([3,1,2]) = 1, \quad \operatorname{maj}([2,1]) = 1.$$
Observe that the sum of the major code of $\sigma$ equals the major index of $\sigma$.
The Lehmer code encodes the inversions of a permutation and the major code encodes its major index. In particular, the number of inversions of a permutation equals the major index of its image under this map.
* The Lehmer code of a permutation $\sigma$ is given by $L(\sigma) = l_1 \ldots l_n$ with $l_i = \# \{ j > i : \sigma_j < \sigma_i \}$. In particular, $l_i$ is the number of boxes in the $i$-th column of the Rothe diagram. For example, the Lehmer code of $\sigma = [4,3,1,5,2]$ is $32010$. The Lehmer code $L : \mathfrak{S}_n\ \tilde\longrightarrow\ S_n$ is a bijection between permutations of size $n$ and sequences $l_1\ldots l_n \in \mathbf{N}^n$ with $l_i \leq i$.
* The major code $M(\sigma)$ of a permutation $\sigma \in \mathfrak{S}_n$ is a way to encode a permutation as a sequence $m_1 m_2 \ldots m_n$ with $m_i \geq i$. To define $m_i$, let $\operatorname{del}_i(\sigma)$ be the normalized permutation obtained by removing all $\sigma_j < i$ from the one-line notation of $\sigma$. The $i$-th index is then given by
$$m_i = \operatorname{maj}(\operatorname{del}_i(\sigma)) - \operatorname{maj}(\operatorname{del}_{i-1}(\sigma)).$$
For example, the permutation $[9,3,5,7,2,1,4,6,8]$ has major code $[5, 0, 1, 0, 1, 2, 0, 1, 0]$ since
$$\operatorname{maj}([8,2,4,6,1,3,5,7]) = 5, \quad \operatorname{maj}([7,1,3,5,2,4,6]) = 5, \quad \operatorname{maj}([6,2,4,1,3,5]) = 4,$$
$$\operatorname{maj}([5,1,3,2,4]) = 4, \quad \operatorname{maj}([4,2,1,3]) = 3, \quad \operatorname{maj}([3,1,2]) = 1, \quad \operatorname{maj}([2,1]) = 1.$$
Observe that the sum of the major code of $\sigma$ equals the major index of $\sigma$.
Map
to 312-avoiding permutation
Description
Return a 312-avoiding permutation corresponding to a binary tree.
The linear extensions of a binary tree form an interval of the weak order called the Sylvester class of the tree. This permutation is the minimal element of this Sylvester class.
The linear extensions of a binary tree form an interval of the weak order called the Sylvester class of the tree. This permutation is the minimal element of this Sylvester class.
Map
to binary tree: right brother = right child
Description
Return a binary tree of size $n-1$ (where $n$ is the size of an ordered tree $t$) obtained from $t$ by the following recursive rule:
- if $x$ is the right brother of $y$ in $t$, then $x$ becomes the right child of $y$;
- if $x$ is the first child of $y$ in $t$, then $x$ becomes the left child of $y$,
and removing the root of $t$.
- if $x$ is the right brother of $y$ in $t$, then $x$ becomes the right child of $y$;
- if $x$ is the first child of $y$ in $t$, then $x$ becomes the left child of $y$,
and removing the root of $t$.
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!