Major index
The major index, also known as the greater index, is a key combinatorial statistic defined on permutations in the symmetric group \mathfrak{S}_n, where it equals the sum of the positions j (for $1 \leq j < n) at which the permutation \sigma exhibits a descent, meaning \sigma(j) > \sigma(j+1).[1] Formally, \operatorname{maj}(\sigma) = \sum_{\substack{1 \leq j < n \\ \sigma(j) > \sigma(j+1)}} j.[1] This statistic, introduced in the context of q-analogs of combinatorial objects, plays a central role in enumerative combinatorics by providing a refined count of permutations that aligns with algebraic structures like the q-factorial.[1]
One of the most notable properties of the major index is its equidistribution with the classical inversion number, another fundamental permutation statistic that counts the number of inverted pairs i < j with \sigma(i) > \sigma(j).[1] Specifically, the generating function for the major index over all n-permutations is identical to that for inversions: \sum_{\sigma \in \mathfrak{S}_n} q^{\operatorname{maj}(\sigma)} = \sum_{\sigma \in \mathfrak{S}_n} q^{\operatorname{inv}(\sigma)} = \prod_{j=1}^n \frac{1 - q^j}{1 - q} = _q!, where _q! denotes the q-factorial.[1] This equality underscores deep symmetries in permutation enumeration and has implications for the study of q-series and symmetric functions.[1]
The major index is intimately connected to Eulerian numbers \left\langle \begin{smallmatrix} n \\ k \end{smallmatrix} \right\rangle, which count the number of n-permutations with exactly k descents (or equivalently, k excedances or k+1 weak excedances).[1] The Eulerian polynomial A_n(q) = \sum_{k=0}^{n-1} \left\langle \begin{smallmatrix} n \\ k \end{smallmatrix} \right\rangle q^{k+1} generates these counts, and while it differs from the major index generating function, both contribute to broader frameworks in algebraic combinatorics, such as the expansion of q-analogs of factorials and connections to the geometry of the permutohedron.[1] Extensions of the major index have been generalized to other combinatorial objects, including standard Young tableaux and set partitions, facilitating refined enumerations in representation theory and symmetric group actions.[2]
Definition
In combinatorics, a permutation \pi of the set = \{1, 2, \dots, n\} is a bijective function from $$ to itself, often represented as the sequence \pi(1) \pi(2) \dots \pi(n).[1]
A position i with $1 \leq i < n is called a descent of \pi if \pi(i) > \pi(i+1). The major index of \pi, denoted \operatorname{maj}(\pi), is defined as the sum of all such descent positions:
\operatorname{maj}(\pi) = \sum_{\substack{1 \leq i < n \\ \pi(i) > \pi(i+1)}} i.
[1]
This statistic was originally introduced by Percy MacMahon in the context of generating functions for permutations.[3]
The major index extends naturally to finite words (or sequences) over the positive integers. For a word w = w_1 w_2 \dots w_n of length n, the descents are the positions i where w_i > w_{i+1}, and \operatorname{maj}(w) is the sum of these positions, analogous to the permutation case.[4]
Descent sets
In the context of permutations, a descent is defined as a position i in a permutation \pi of = \{1, 2, \dots, n\} such that \pi(i) > \pi(i+1).[1] This condition identifies locations where the sequence decreases between consecutive elements.[4]
The descent set, denoted \operatorname{Des}(\pi) or D(\pi), is the set of all such descent positions \{i \mid \pi(i) > \pi(i+1), 1 \leq i \leq n-1\}.[5] By construction, \operatorname{Des}(\pi) forms a subset of \{1, 2, \dots, n-1\}, capturing the structural drops in the permutation's order.[4] For the identity permutation, which is strictly increasing, the descent set is empty, indicating no such decreases occur.[4]
The descent set provides the foundational combinatorial object for the major index, where \operatorname{maj}(\pi) is the sum of the elements in \operatorname{Des}(\pi).[1] This relation underscores the descent set's role in aggregating positional information to yield the statistic.[5]
Examples and computation
Basic examples
The major index of a permutation can be illustrated through simple examples in the symmetric group S_3, consisting of all permutations of the set {1, 2, 3}. A descent occurs at position i if \pi_i > \pi_{i+1}, and the major index is the sum of such positions i.[6]
Consider the permutation \pi = [1](/page/1)\, [3\, 2](/page/3-2). There is a descent at i=2 since [3 > 2](/page/3-2), so the descent set is {2} and \maj(\pi) = [2](/page/1).[6]
For the permutation \pi = [3\, 1\, 2](/page/3-2), there is a descent at i=1 since [3 > 1](/page/3-2), so the descent set is {1} and \maj(\pi) = [1](/page/1).[6]
The identity permutation \pi = [1](/page/1)\, [2](/page/1)\, [3](/page/1) has no descents, so the descent set is empty and \maj(\pi) = 0.[6]
For a complete visualization in S_3, the table below lists all six permutations, their descent sets, and major indices:
| Permutation | Descent Set | Major Index |
|---|
| 123 | ∅ | 0 |
| 132 | {2} | 2 |
| 213 | {1} | 1 |
| 231 | {2} | 2 |
| 312 | {1} | 1 |
| 321 | {1,2} | 3 |
Algorithmic computation
The major index of a permutation \pi = \pi_1 \pi_2 \cdots \pi_n \in S_n is computed by identifying the descent set D(\pi) = \{i \mid 1 \leq i \leq n-1, \pi_i > \pi_{i+1}\} and summing its elements, as defined by Stanley.[6]
A straightforward linear-time algorithm achieves this by performing a single pass through the permutation, checking each adjacent pair for a descent and accumulating the position i (using 1-based indexing) when one occurs. This approach directly implements the definition without requiring additional data structures beyond storage for \pi.
The following pseudocode illustrates the computation:
function major_index(π: array of size n):
maj = 0
for i = 1 to n-1:
if π[i] > π[i+1]:
maj += i
return maj
function major_index(π: array of size n):
maj = 0
for i = 1 to n-1:
if π[i] > π[i+1]:
maj += i
return maj
This algorithm runs in O(n) time complexity, as it involves exactly n-1 comparisons and additions in the worst case, and uses O(1) additional space excluding the input permutation.[6]
For practical implementation, the algorithm is well-suited to programming languages such as Python due to its simplicity and efficiency for large n. Edge cases include the empty permutation or n=1, where the major index is 0 by convention, as there are no possible descents.[6]
Properties
Symmetry and equidistribution
The major index of a permutation \pi \in S_n ranges from 0, achieved by the identity permutation, to \binom{n}{2}, achieved by the reverse permutation n \cdots 1.
A fundamental symmetry of the major index is its equidistribution with the inversion number \mathrm{inv}(\pi), defined as the sum of the entries in the inversion table of \pi. Specifically, for each fixed n and k, the number of permutations \pi \in S_n with \mathrm{maj}(\pi) = k equals the number with \mathrm{inv}(\pi) = k. This equidistribution, originally established by MacMahon using generating functions, implies that the major index and inversion number share the same distribution over S_n.
The common distribution is captured by the Mahonian numbers M_{n,k} = |\{\pi \in S_n \mid \mathrm{maj}(\pi) = k\}|, which count permutations by major index (or equivalently by inversions). The generating function for these numbers is the q-factorial
_q! = \sum_{k=0}^{\binom{n}{2}} M_{n,k} q^k = \prod_{i=1}^n \frac{1 - q^i}{1 - q},
a q-analog of the factorial that interpolates the uniform distribution at q=1.
This equidistribution can be established combinatorially via explicit bijections between permutations that preserve the respective statistics. One such bijective proof constructs a map using inversion tables: for a permutation of length n, the inversion table entries a_j (with $0 \leq a_j \leq j) satisfy \mathrm{inv}(\pi) = \sum a_j, and inserting the value n into the permutation increases \mathrm{maj}(\pi) by exactly a_{n-1} at the corresponding position, inductively matching the counts for all k.
q-analog connections
The generating function for the major index over all permutations in the symmetric group S_n is the q-analog of n!, expressed as
\sum_{\pi \in S_n} q^{\mathrm{maj}(\pi)} = _q! = \prod_{k=1}^n \frac{1 - q^k}{1 - q}.
This formula, originally established by MacMahon, demonstrates how the major index provides a combinatorial basis for the q-deformation of the factorial.[7]
The major index also connects to Kostka polynomials through the Robinson-Schensted-Knuth correspondence, which associates permutations \pi to pairs of standard Young tableaux; here, \mathrm{maj}(\pi) equals the major index of the insertion tableau, providing a weighting for terms in the q-Kostka polynomials. In particular, for the straight shape case with content (1^n), the generating function \sum_T q^{\mathrm{maj}(T)} over standard Young tableaux T of shape \lambda yields the Kostka-Foulkes polynomial K_{\lambda, (1^n)}(q).[8]
This q-analog refines the uniform distribution of permutations (recovered at q=1) by positionally weighting descents in the major index, thereby encoding additional structural information about permutation descents.[7]
Historical development
Origins in combinatorics
The major index, originally termed the "greater index" by its introducer, emerged in the early 20th century as a key statistic in enumerative combinatorics, particularly for analyzing permutations. Percy Alexander MacMahon, a British mathematician and army major, first defined it in his 1913 paper on the indices of permutations, where he considered sequences of distinct or repeated elements and introduced two primary indices: the "lesser index" (the count of descents) and the greater index (the sum of the positions of those descents). The name "major index" was later suggested by Dominique Foata in honor of MacMahon's rank as a Major. This definition arose from MacMahon's broader investigations into generating functions associated with permutations of any assemblage of objects, motivated by the need to derive symmetric functions and probability-generating expressions for permutation statistics.
MacMahon's work built on foundational studies of descents, which trace back to earlier combinatorial explorations but gained prominence through his emphasis on their role in the cycle index of the symmetric group S_n and related generating functions. The greater index provided a weighted measure of descents, enabling the construction of q-analogues and refinements to classical enumerations, such as those for inversions. In this context, it linked permutation patterns to more general symmetric group statistics, including applications in plane partitions, where MacMahon extended descent-like concepts to multidimensional arrays in his contemporaneous research.[9]
The key publication formalizing these ideas appeared in MacMahon's two-volume "Combinatory Analysis" (1915–1916), where the major index appears implicitly through sums over descent positions in the enumeration of permutations and related structures. Early applications focused on enumerating permutations by their descent statistics, notably establishing that the generating function for the major index equals that for the inversion number, a result MacMahon proved using algebraic manipulations of symmetric functions. This equidistribution theorem underscored the statistic's utility in partitioning the symmetric group S_n and laid groundwork for subsequent combinatorial identities.[9][10]
Key contributions
In the 1970s, Dominique Foata, in collaboration with Marcel-Paul Schützenberger, established a fundamental bijection between permutations based on their major index and inversion table, providing a combinatorial proof of the equidistribution of the major index and the inversion number over the symmetric group. This work refined earlier generating function approaches by MacMahon and introduced explicit transformations, such as the Foata bijection, that preserve these statistics while mapping between distinct combinatorial objects. Their results, published in 1978, solidified the major index as a tool for bijective proofs in permutation enumeration.[3]
During the 1980s, Adriano Garsia and Jeffrey Remmel advanced the theory through q-analogs and multivariate extensions of the major index, particularly in the context of permutation shuffles and their connections to Kronecker products of representations. Their 1985 paper on shuffles of permutations demonstrated how the major index interacts with q-deformations in generating functions for symmetric group actions, enabling refinements that track multiple descent-like features simultaneously. These contributions facilitated broader applications in algebraic combinatorics, including interpretations of q-Mahonian distributions via rook placements and derangement analogs.
Richard Stanley's 1986 monograph Enumerative Combinatorics played a pivotal role in canonizing the major index as a core permutation statistic, offering detailed expositions of its properties, equidistributions, and enumerative formulas alongside other statistics like inversions and descents. By integrating the major index into the broader framework of Mahonian numbers and q-series, Stanley's treatment emphasized its symmetry and utility in proving classical identities, such as those involving Eulerian polynomials. This survey work, updated in subsequent editions, has served as a foundational reference, influencing generations of research in the field.
Post-2000 developments have extended the major index to affine permutations within the affine symmetric group, revealing connections to representation theory and crystal bases of Lie algebras. For instance, Jason Fulman's 1999 study of affine shuffles introduced modular refinements of the major index distribution over conjugacy classes, linking it to modular representations of the symmetric group.[11] Further, works like Carlsson, Freyr, and Lam's 2018 exploration of affine Schubert calculus incorporate the major index in q-analogs of double coinvariants, bridging combinatorial statistics with geometric and algebraic structures in quantum Lie theory, including crystal operator actions on affine permutation tableaux.
Applications
In permutation statistics
The major index serves as a descent statistic on permutations, defined for a permutation \sigma \in S_n as \operatorname{maj}(\sigma) = \sum_{i \in \operatorname{Des}(\sigma)} i, where \operatorname{Des}(\sigma) = \{i : 1 \leq i < n, \sigma(i) > \sigma(i+1)\} is the descent set.[12] Unlike the descent number \operatorname{des}(\sigma) = |\operatorname{Des}(\sigma)|, which counts the total number of descents and is equidistributed with the excedance number to yield the Eulerian numbers, the major index weights each descent by its position, providing a refined measure that leads to the Mahonian numbers as its distribution over S_n.[12]
Refinements of the major index often involve joint distributions with other permutation statistics, such as the excedance number \operatorname{exc}(\sigma) = |\{i : \sigma(i) > i\}| or the cycle type. The bivariate generating function \sum_{\sigma \in S_n} q^{\operatorname{maj}(\sigma)} t^{\operatorname{exc}(\sigma)} admits a closed form involving q-exponential functions: \sum_{n \geq 0} A_{\operatorname{maj},\operatorname{exc},n}(q,t) \frac{z^n}{_q!} = (1 - tq) \exp_q(z) \exp_q(ztq) - tq \exp_q(z), highlighting equidistribution properties between major index and inversions alongside excedances.[12]
In the context of pattern avoidance, the major index has been studied on classes like 132-avoiding permutations S_n(132), where the bivariate generating function \sum_{\sigma \in S_n(132)} q^{\operatorname{maj}(\sigma)} t^{\operatorname{des}(\sigma)} reveals non-unimodal and non-symmetric behaviors for certain descent counts; for instance, the coefficient for two descents is non-unimodal for n \geq 5.[13] Explicit formulas include, for one descent, \sum_{i=1}^{n-1} (n-i) q^i t, and more complex polynomial expressions for higher descents that demonstrate the statistic's asymmetry in this class.[13]
Recent work has extended the major index to colored permutation groups and other structures, including proofs of equidistribution conjectures over trees.[14]
For computational enumeration, the major index facilitates the generation of Mahonian distributions in software like SageMath, which supports efficient computation of permutation statistics up to n=20 via its combinatorial class framework for S_n, allowing enumeration of the distribution without exhaustive generation of all n! elements.[15]
In representation theory
In the representation theory of the symmetric group S_n, Specht modules S^\lambda indexed by partitions \lambda \vdash n provide the irreducible representations over \mathbb{C}. These modules admit a basis consisting of standard Young tableaux of shape \lambda, where a standard Young tableau T is a filling of the Young diagram of \lambda with numbers $1 through n increasing across rows and down columns. The major index extends naturally to such tableaux via the descent set: a descent in T occurs at position i if i+1 appears strictly below i in the diagram, and \maj(T) is defined as the sum of these descent positions. This statistic equips the Specht module with a grading that refines its structure, facilitating computations in character theory and connections to symmetric functions.[16]
A notable application arises in the analysis of the longest element w_0 \in S_n, the reverse permutation sending i to n+1-i. Its descent set comprises all positions $1 \leq i < n, yielding \maj(w_0) = \sum_{i=1}^{n-1} i = \binom{n}{2}, which matches the Coxeter length \ell(w_0) in the symmetric group's presentation as a Coxeter group. This equality underscores the major index's alignment with the geometric and algebraic length functions central to Coxeter theory, bridging combinatorial statistics with the module's highest-weight structure.[16]
The major index further features in q-deformations of Frobenius characters via the cyclic sieving phenomenon. For the action of the cyclic subgroup C_n \leq S_n on the set of standard Young tableaux of shape \lambda, the polynomial \sum_{T \in \SYT(\lambda)} x^{\maj(T)} cyclically sieves under the cyclic action, with eigenvalues tied to roots of unity. Specifically, the Kraskiewicz–Weyman theorem equates the number of tableaux T with \maj(T) \equiv r \pmod{n} to the multiplicity \langle S^\lambda, \chi_r \uparrow^{S_n}_{C_n} \rangle, where \chi_r is the r-th cyclotomic character; this refines the Frobenius character by tracking modular major indices, resolving conjectures on the distribution and existence of such tableaux except for exceptional shapes like the hook or staircase partitions.[17]
In the Hecke algebra H_n(q), the q-analog of the group algebra \mathbb{Q}[S_n], the major index generates key deformation parameters through its Mahonian distribution: the generating function \sum_{\pi \in S_n} q^{\maj(\pi)} = !_q, the q-factorial, equals the Poincaré series of H_n(q) graded by the Coxeter length, owing to the equidistribution of major index and inversions over S_n.