- FindStat

Identifier

Mp00073: Permutations —major-index to inversion-number bijection⟶ Permutations
Mp00252: Permutations —restriction⟶ Permutations
Mp00062: Permutations —Lehmer-code to major-code bijection⟶ Permutations
St000325: Permutations ⟶ ℤ (values match St000021The number of descents of a permutation., St000470The number of runs in a permutation.)

Values

[1,2] => [1,2] => [1] => [1] => 1

[2,1] => [2,1] => [1] => [1] => 1

[1,2,3] => [1,2,3] => [1,2] => [1,2] => 1

[1,3,2] => [2,3,1] => [2,1] => [2,1] => 2

[2,1,3] => [2,1,3] => [2,1] => [2,1] => 2

[2,3,1] => [3,1,2] => [1,2] => [1,2] => 1

[3,1,2] => [1,3,2] => [1,2] => [1,2] => 1

[3,2,1] => [3,2,1] => [2,1] => [2,1] => 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[1,2,3,4,5] => [1,2,3,4,5] => [1,2,3,4] => [1,2,3,4] => 1

[1,2,3,5,4] => [2,3,4,5,1] => [2,3,4,1] => [1,2,4,3] => 2

[1,2,4,3,5] => [2,3,4,1,5] => [2,3,4,1] => [1,2,4,3] => 2

[1,2,4,5,3] => [2,3,5,1,4] => [2,3,1,4] => [1,3,2,4] => 2

[1,2,5,3,4] => [2,3,1,5,4] => [2,3,1,4] => [1,3,2,4] => 2

[1,2,5,4,3] => [3,4,5,2,1] => [3,4,2,1] => [1,4,3,2] => 3

[1,3,2,4,5] => [2,3,1,4,5] => [2,3,1,4] => [1,3,2,4] => 2

[1,3,2,5,4] => [3,4,2,5,1] => [3,4,2,1] => [1,4,3,2] => 3

[1,3,4,2,5] => [2,4,1,3,5] => [2,4,1,3] => [1,3,4,2] => 2

[1,3,4,5,2] => [2,5,1,3,4] => [2,1,3,4] => [2,1,3,4] => 2

[1,3,5,2,4] => [2,1,4,5,3] => [2,1,4,3] => [1,4,2,3] => 2

[1,3,5,4,2] => [3,5,2,4,1] => [3,2,4,1] => [2,1,4,3] => 3

[1,4,2,3,5] => [2,1,4,3,5] => [2,1,4,3] => [1,4,2,3] => 2

[1,4,2,5,3] => [3,4,5,1,2] => [3,4,1,2] => [3,1,4,2] => 3

[1,4,3,2,5] => [3,4,2,1,5] => [3,4,2,1] => [1,4,3,2] => 3

[1,4,3,5,2] => [3,5,2,1,4] => [3,2,1,4] => [3,2,1,4] => 3

[1,4,5,2,3] => [2,1,5,3,4] => [2,1,3,4] => [2,1,3,4] => 2

[1,4,5,3,2] => [3,5,4,1,2] => [3,4,1,2] => [3,1,4,2] => 3

[1,5,2,3,4] => [2,1,3,5,4] => [2,1,3,4] => [2,1,3,4] => 2

[1,5,2,4,3] => [3,2,5,4,1] => [3,2,4,1] => [2,1,4,3] => 3

[1,5,3,2,4] => [3,4,1,5,2] => [3,4,1,2] => [3,1,4,2] => 3

[1,5,3,4,2] => [3,5,1,4,2] => [3,1,4,2] => [4,2,1,3] => 3

[1,5,4,2,3] => [3,1,5,4,2] => [3,1,4,2] => [4,2,1,3] => 3

[1,5,4,3,2] => [4,5,3,2,1] => [4,3,2,1] => [4,3,2,1] => 4

[2,1,3,4,5] => [2,1,3,4,5] => [2,1,3,4] => [2,1,3,4] => 2

[2,1,3,5,4] => [3,2,4,5,1] => [3,2,4,1] => [2,1,4,3] => 3

[2,1,4,3,5] => [3,2,4,1,5] => [3,2,4,1] => [2,1,4,3] => 3

[2,1,4,5,3] => [3,2,5,1,4] => [3,2,1,4] => [3,2,1,4] => 3

[2,1,5,3,4] => [3,2,1,5,4] => [3,2,1,4] => [3,2,1,4] => 3

[2,1,5,4,3] => [4,3,5,2,1] => [4,3,2,1] => [4,3,2,1] => 4

[2,3,1,4,5] => [3,1,2,4,5] => [3,1,2,4] => [2,3,1,4] => 2

[2,3,1,5,4] => [4,2,3,5,1] => [4,2,3,1] => [2,4,3,1] => 3

[2,3,4,1,5] => [4,1,2,3,5] => [4,1,2,3] => [2,3,4,1] => 2

[2,3,4,5,1] => [5,1,2,3,4] => [1,2,3,4] => [1,2,3,4] => 1

[2,3,5,1,4] => [1,3,4,5,2] => [1,3,4,2] => [2,4,1,3] => 2

[2,3,5,4,1] => [5,2,3,4,1] => [2,3,4,1] => [1,2,4,3] => 2

[2,4,1,3,5] => [1,3,4,2,5] => [1,3,4,2] => [2,4,1,3] => 2

[2,4,1,5,3] => [4,2,5,1,3] => [4,2,1,3] => [3,2,4,1] => 3

[2,4,3,1,5] => [4,2,3,1,5] => [4,2,3,1] => [2,4,3,1] => 3

[2,4,3,5,1] => [5,2,3,1,4] => [2,3,1,4] => [1,3,2,4] => 2

[2,4,5,1,3] => [1,3,5,2,4] => [1,3,2,4] => [3,1,2,4] => 2

[2,4,5,3,1] => [5,2,4,1,3] => [2,4,1,3] => [1,3,4,2] => 2

[2,5,1,3,4] => [1,3,2,5,4] => [1,3,2,4] => [3,1,2,4] => 2

[2,5,1,4,3] => [2,4,5,3,1] => [2,4,3,1] => [4,1,3,2] => 3

[2,5,3,1,4] => [4,2,1,5,3] => [4,2,1,3] => [3,2,4,1] => 3

[2,5,3,4,1] => [5,2,1,4,3] => [2,1,4,3] => [1,4,2,3] => 2

[2,5,4,1,3] => [1,4,5,3,2] => [1,4,3,2] => [4,3,1,2] => 3

[2,5,4,3,1] => [5,3,4,2,1] => [3,4,2,1] => [1,4,3,2] => 3

[3,1,2,4,5] => [1,3,2,4,5] => [1,3,2,4] => [3,1,2,4] => 2

[3,1,2,5,4] => [2,4,3,5,1] => [2,4,3,1] => [4,1,3,2] => 3

[3,1,4,2,5] => [3,4,1,2,5] => [3,4,1,2] => [3,1,4,2] => 3

[3,1,4,5,2] => [3,5,1,2,4] => [3,1,2,4] => [2,3,1,4] => 2

[3,1,5,2,4] => [3,1,4,5,2] => [3,1,4,2] => [4,2,1,3] => 3

[3,1,5,4,2] => [4,5,2,3,1] => [4,2,3,1] => [2,4,3,1] => 3

[3,2,1,4,5] => [3,2,1,4,5] => [3,2,1,4] => [3,2,1,4] => 3

[3,2,1,5,4] => [4,3,2,5,1] => [4,3,2,1] => [4,3,2,1] => 4

[3,2,4,1,5] => [4,2,1,3,5] => [4,2,1,3] => [3,2,4,1] => 3

[3,2,4,5,1] => [5,2,1,3,4] => [2,1,3,4] => [2,1,3,4] => 2

[3,2,5,1,4] => [1,4,3,5,2] => [1,4,3,2] => [4,3,1,2] => 3

[3,2,5,4,1] => [5,3,2,4,1] => [3,2,4,1] => [2,1,4,3] => 3

[3,4,1,2,5] => [1,4,2,3,5] => [1,4,2,3] => [3,4,1,2] => 2

[3,4,1,5,2] => [4,5,1,2,3] => [4,1,2,3] => [2,3,4,1] => 2

[3,4,2,1,5] => [4,3,1,2,5] => [4,3,1,2] => [3,4,2,1] => 3

[3,4,2,5,1] => [5,3,1,2,4] => [3,1,2,4] => [2,3,1,4] => 2

[3,4,5,1,2] => [1,5,2,3,4] => [1,2,3,4] => [1,2,3,4] => 1

[3,4,5,2,1] => [5,4,1,2,3] => [4,1,2,3] => [2,3,4,1] => 2

[3,5,1,2,4] => [1,2,4,5,3] => [1,2,4,3] => [4,1,2,3] => 2

[3,5,1,4,2] => [2,5,3,4,1] => [2,3,4,1] => [1,2,4,3] => 2

[3,5,2,1,4] => [4,1,3,5,2] => [4,1,3,2] => [4,2,3,1] => 3

>>> Load all 5912 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 width of the tree associated to a permutation.
A permutation can be mapped to a rooted tree with vertices $\{0,1,2,\ldots,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 width of the tree is given by the number of leaves of this tree.
Note that, due to the construction of this tree, the width of the tree is always one more than the number of descents St000021The number of descents of a permutation.. This also matches the number of runs in a permutation St000470The number of runs in a permutation..
See also St000308The height of the tree associated to a permutation. for the height of this tree.

Map

major-index to inversion-number bijection

Description

Return the permutation whose Lehmer code equals the major code of the preimage.
This map sends the major index to the number of inversions.

Map

restriction

Description

The permutation obtained by removing the largest letter.
This map is undefined for the empty permutation.

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$.