Permutation statistics and linear extensions of posets
From MaRDI portal
(Redirected from Publication:1177948)
The relation between two permutation statistics --- the inversion index and the major index --- are studied. For a permutation \(\sigma=\sigma_ 1\sigma_ 2\cdots\sigma_ n\), the inversion index is the number of ordered pairs \((i,j)\) such that \(i<j\) and \(\sigma_ i>\sigma_ j\); the major index is the sum of all \(i\) such that \(\sigma_ i>\sigma_{i+1}\). By a theorem of MacMahon these statistics are equidistributed on \(S_ n\), i.e., the number of permutations with a given inversion index coincides with the number of those having the same major index. Foata's bijection takes \(maj\) to \(inv\) and so justifies this result. The subsets \(U\) of \(S_ n\) for which these statistics are equidistributed are characterized; this extends the previous results of Foata, Schützenberger, and the authors. The characterization is complete when \(U\) is a set of linear extensions of a naturally labeled poset \(P\); in this case \(U\) must be invariant under Foata's bijection, and \(P\) should be a postorder labeled forest. The intervals in the weak Bruhat order of \(S_ n\) are also studied from the same viewpoint.
Recommendations
Cites work
- A q-analog of the exponential formula
- Buildings of spherical type and finite BN-pairs
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Enumeration of permutations by descents, idescents, imajor index, and basic components
- Generalized Quotients in Coxeter Groups
- scientific article; zbMATH DE number 3811868 (Why is no real title available?)
- scientific article; zbMATH DE number 3983158 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- scientific article; zbMATH DE number 3216769 (Why is no real title available?)
- Major Index and Inversion Number of Permutations
- On the Netto Inversion Number of a Sequence
- Ordered structures and partitions
- Partial orderings of permutations and monotonicity of a rank correlation statistic
- Principles of combinatorics
- q-hook length formulas for forests
- Restricted permutations
- The 3-Irreducible Partially Ordered Sets
Cited in
(92)- Some statistics for Fibonacci tableaux
- Enumerating S_n by associated transpositions and linear extensions of finite posets
- Mahonian statistics on labeled forests
- Enumeration of functions from posets to chains
- Permutation statistics of indexed permutations
- Metrics on permutations useful for positive dependence
- Noncommutative Bell polynomials and the dual immaculate basis
- The weak order on integer posets
- A simple transformation for Mahonian statistics on labelings of rake posets
- Linear extensions of ranked posets, enumerated by descents. A problem of Stanley from the 1981 Banff conference on ordered sets
- An analogue of the plactic monoid for binary search trees
- Bipartition orders and statistics on words
- Invariant principal order ideals under Foata's transformation
- An exponential formula for polynomial vector fields. II: Lie series, exponential substitution, and rooted trees
- Weighted-inversion statistics and their symmetry groups
- Shuffle-compatible permutation statistics. II: The exterior peak set
- Separable elements and splittings of Weyl groups
- A polynomial time algorithm for the 2-poset cover problem
- Whitney numbers for poset cones
- Statistics on multipermutations and partial \(\gamma\)-positivity
- Statistics of partial permutations via Catalan matrices
- Troupes, cumulants, and stack-sorting
- Mahonian and Euler-Mahonian statistics for set partitions
- Polyurethane toggles
- Separable elements: linear extensions, graph associahedra, and splittings of Weyl groups
- Counting linear extensions of restricted posets
- Counting smaller elements in the Tamari and \(m\)-Tamari lattices
- Statistics on wreath products and generalized binomial-Stirling numbers
- Symmetry and log-concavity results for statistics on Fibonacci tableaux
- A refinement of weak order intervals into distributive lattices
- The sorting index and equidistribution of set-valued statistics over restricted permutations
- Some remarks on sign-balanced and maj-balanced posets
- Equi-distribution over descent classes of the hyperoctahedral group
- Properties of four partial orders on standard Young tableaux
- Linear extension diameter of level induced subposets of the Boolean lattice
- Algebraic structures on integer posets
- Linear extension numbers of \(n\)-element posets
- Research problem: combinatorial and multilinear aspects of sign-balanced posets
- The sorting index and inversion number on order ideals of permutation groups
- Sorting index and Mahonian-Stirling pairs for labeled forests
- Major index distribution over permutation classes
- Signed words and permutations, I: A fundamental transformation
- scientific article; zbMATH DE number 5163456 (Why is no real title available?)
- Multivariate generalizations of the Foata-Schützenberger equidistribution
- Multibasic Eulerian Polynomials
- Product decompositions of the symmetric group induced by separable permutations
- Linear extension sums as valuations on cones
- Shellable nonpure complexes and posets. II
- A poset view of the major index.
- Inner tableau translation property of the weak order and related results
- Generalized Dyck tilings
- Friends and strangers walking on graphs
- The hull metric on Coxeter groups
- The height of a permutation and applications to distance between real line arrangements
- The algebra of binary search trees
- Counting linear extensions of posets with determinants of hook lengths
- Geometric inequalities for anti-blocking bodies
- Permutrees
- Sign-balanced posets
- Counting derangements with signed right-to-left minima and excedances
- Han's bijection via permutation codes
- Mahonian-Stirling statistics for partial permutations
- Poset modules of the 0-Hecke algebras and related quasisymmetric power sum expansions
- Log-concave poset inequalities
- Mahonian pairs
- Permutation statistics for a percolation model on \(\mathbb{Z}^2\) with imposed symmetries
- Tree expansions of some Lie idempotents
- Correlation inequalities for linear extensions
- Acyclic reorientation lattices and their lattice quotients
- Regular Schur labeled skew shape posets and their 0-Hecke modules
- On the lattice of the weak factorization systems on a finite lattice
- Interval hypergraphic lattices
- Construction numbers: how to build a graph
- Quasisymmetric Schur Q-functions and peak Young quasisymmetric Schur functions
- Coloured shuffle compatibility, Hadamard products, and ask zeta functions
- Lattices of acyclic pipe dreams
- Equivalence classes of lower and upper descent weak Bruhat intervals
- Combinatorial results on barcode lattices
- Combinatorics of rectangulations: old and new bijections
- Shuffles of deformed permutahedra, multiplihedra, constrainahedra, and biassociahedra
- Classification of weak Bruhat interval modules of 0-Hecke algebras
- Regular Schur labeled skew shape posets and their 0-Hecke modules
- The Hopf algebra of integer binary relations
- Linear extensions of finite posets and a conjecture of G. Kreweras on permutations
- A unified construction of Coxeter group representations.
- Introduction to partially ordered patterns
- q-hook length formulas for forests
- Fix-Mahonian calculus. III: a quadruple distribution
- Trees, functional equations, and combinatorial Hopf algebras
- Fix-Mahonian calculus. II: Further statistics
- Enumeration by associated reflections on Coxeter systems
- Posets and permutations in the duplication-loss model: minimal permutations with \(d\) descents
This page was built for publication: Permutation statistics and linear extensions of posets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1177948)
