Identifier
St000027:
Dyck paths
⟶ ℤ
Values
No modified entries
Description
The major index of a Dyck path.
This is the sum over all $i$ for which $(i,j)$ is a valley of $D$.
The generating function of the major index yields MacMahon 's $q$-Catalan numbers
$$\sum_{D \in \mathfrak{D}_n} q^{\operatorname{maj}(D)} = \frac{1}{[n+1]_q}\begin{bmatrix} 2n \\ n \end{bmatrix}_q,$$
where $[k]_q := 1+q+\ldots+q^{k-1}$ is the usual $q$-extension of the integer $k$, $[k]_q!:= [1]_q[2]_q \cdots [k]_q$ is the $q$-factorial of $k$ and $\left[\begin{smallmatrix} k \\ l \end{smallmatrix}\right]_q:=[k]_q!/[l]_q![k-l]_q!$ is the $q$-binomial coefficient.
The major index was first studied by P.A.MacMahon in [1], where he proved this generating function identity.
There is a bijection $\psi$ between Dyck paths and noncrossing permutations which simultaneously sends the area of a Dyck path St000012The area of a Dyck path. to the number of inversions St000018The number of inversions of a permutation., and the major index of the Dyck path to $n(n-1)$ minus the sum of the major index and the major index of the inverse [2].
For the major index on other collections, see St000004The major index of a permutation. for permutations and St000290The major index of a binary word. for binary words.
This is the sum over all $i$ for which $(i,j)$ is a valley of $D$.
The generating function of the major index yields MacMahon 's $q$-Catalan numbers
$$\sum_{D \in \mathfrak{D}_n} q^{\operatorname{maj}(D)} = \frac{1}{[n+1]_q}\begin{bmatrix} 2n \\ n \end{bmatrix}_q,$$
where $[k]_q := 1+q+\ldots+q^{k-1}$ is the usual $q$-extension of the integer $k$, $[k]_q!:= [1]_q[2]_q \cdots [k]_q$ is the $q$-factorial of $k$ and $\left[\begin{smallmatrix} k \\ l \end{smallmatrix}\right]_q:=[k]_q!/[l]_q![k-l]_q!$ is the $q$-binomial coefficient.
The major index was first studied by P.A.MacMahon in [1], where he proved this generating function identity.
There is a bijection $\psi$ between Dyck paths and noncrossing permutations which simultaneously sends the area of a Dyck path St000012The area of a Dyck path. to the number of inversions St000018The number of inversions of a permutation., and the major index of the Dyck path to $n(n-1)$ minus the sum of the major index and the major index of the inverse [2].
For the major index on other collections, see St000004The major index of a permutation. for permutations and St000290The major index of a binary word. for binary words.
Diff Description
The major index of a Dyck path.
This is the sum over all i+j for which (i,j) is a valley of D.
The generating function of the major index yields '''MacMahon''' 's q-Catalan numbers
\sum_{D \in \mathfrak{D}_n} q^{\operatorname{maj}(D)} = \frac{1}{[n+1]_q}\begin{bmatrix} 2n \\ n \end{bmatrix}_q,
where [k]_q := 1+q+\ldots+q^{k-1} is the usual q-extension of the integer k, [k]_q!:= [1]_q[2]_q \cdots [k]_q is the q-factorial of k and \left[\begin{smallmatrix} k \\ l \end{smallmatrix}\right]_q:=[k]_q!/[l]_q![k-l]_q! is the q-binomial coefficient.
The major index was first studied by P.A.MacMahon in [1], where he proved this generating function identity.
There is a bijection \psi between Dyck paths and '''noncrossing permutations''' which simultaneously sends the area of a Dyck path [[St000012]] to the number of inversions [[St000018]], and the major index of the Dyck path to n(n-1) minus the sum of the major index and the major index of the inverse [2].
For the major index on other collections, see [[St000004]] for permutations and [[St000290]] for binary words.
This is the sum over all i
The generating function of the major index yields '''MacMahon''' 's q-Catalan numbers
\sum_{D \in \mathfrak{D}_n} q^{\operatorname{maj}(D)} = \frac{1}{[n+1]_q}\begin{bmatrix} 2n \\ n \end{bmatrix}_q,
where [k]_q := 1+q+\ldots+q^{k-1} is the usual q-extension of the integer k, [k]_q!:= [1]_q[2]_q \cdots [k]_q is the q-factorial of k and \left[\begin{smallmatrix} k \\ l \end{smallmatrix}\right]_q:=[k]_q!/[l]_q![k-l]_q! is the q-binomial coefficient.
The major index was first studied by P.A.MacMahon in [1], where he proved this generating function identity.
There is a bijection \psi between Dyck paths and '''noncrossing permutations''' which simultaneously sends the area of a Dyck path [[St000012]] to the number of inversions [[St000018]], and the major index of the Dyck path to n(n-1) minus the sum of the major index and the major index of the inverse [2].
For the major index on other collections, see [[St000004]] for permutations and [[St000290]] for binary words.
References
[1] MacMahon, P. A. Combinatory analysis MathSciNet:0141605
[2] Stump, C. More bijective Catalan combinatorics on permutations and on signed permutations arXiv:0808.2822
[2] Stump, C. More bijective Catalan combinatorics on permutations and on signed permutations arXiv:0808.2822
Code
def statistic(x):
return x.major_index()
Created
Jun 10, 2012 at 08:35 by Christian Stump
Updated
Aug 28, 2025 at 23:06 by Milena Loper
29 Aug 17:06