Counting permutations with given cycle structure and descent set

DOI10.1016/0097-3165(93)90095-PzbMath0793.05004WikidataQ56625065 ScholiaQ56625065MaRDI QIDQ1318366

Ira M. Gessel, Christophe Reutenauer

Publication date: 10 August 1994

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

zbMATH Keywords

symmetric group; permutation; symmetric functions; cycle structure; descent set

Mathematics Subject Classification ID

05A15: Exact enumeration problems, generating functions

05A05: Permutations, words, matrices

05E05: Symmetric functions and generalizations

Related Items

SORTING CONJUGATES AND SUFFIXES OF WORDS IN A MULTISET, The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words, Indecomposable modules for the dual immaculate basis of quasi-symmetric functions, Applications of the Brauer complex: card shuffling, permutation statistics, and dynamical systems, Inverses of words and the parabolic structure of the symmetric group, A symmetry property of Solomon's algebra and of higher Lie characters, The algebra of quasi-symmetric functions is free over the integers, Chromatic quasisymmetric functions, Descents of \(\lambda\)-unimodal cycles in a character formula, The Pieri rule for dual immaculate quasi-symmetric functions, Analysis of casino shelf shuffling machines, Eulerian quasisymmetric functions for the type B Coxeter group and other wreath product groups, A bijection between words and multisets of necklaces, Enumeration of involutions by descents and symmetric matrices, Matrices, characters and descents, Characterization of the allowed patterns of signed shifts, Schur-positive sets of permutations via products and grid classes, Chromatic symmetric functions of hypertrees, Fix-Euler-Mahonian statistics on wreath products, The decrease value theorem with an application to permutation statistics, A symmetry of the descent algebra of a finite Coxeter group., The formal series Witt transform, Eulerian quasisymmetric functions, The \((1-\mathbb{E})\)-transform in combinatorial Hopf algebras, The ratio monotonicity of the \(q\)-derangement numbers, Unimodality of Eulerian quasisymmetric functions, The limiting distribution of the \(q\)-derangement numbers, Burrows-Wheeler transformations and de Bruijn words, Descent sets of cyclic permutations, Recurrence relations for graph polynomials on bi-iterative families of graphs, Alternating permutations and symmetric functions, \(r\)-Qsym is free over Sym, Modules of the 0-Hecke algebra and quasisymmetric Schur functions, Skew row-strict quasisymmetric Schur functions, Littlewood-Richardson rules for symmetric skew quasisymmetric Schur functions, Signed words and permutations. IV: Fixed and pixed points, Fix-Mahonian calculus. III: a quadruple distribution, Fix-Mahonian calculus. I: Two transformations, Fix-Mahonian calculus. II: Further statistics, Combinatorial Hopf algebras, noncommutative Hall-Littlewood functions, and permutation tableaux, Permutations with extremal number of fixed points, Schur positivity of skew Schur function differences and applications to ribbons and Schubert classes, Carries, shuffling, and symmetric functions, Signed words and permutations. V: A sextuple distribution, A \(q\)-table of Euler, On the spiral property of the \(q\)-derangement numbers, The distribution of descents in fixed conjugacy classes of the symmetric groups, A combinatorial interpretation of the Seidel generation of \(q\)-derangement numbers, Descent classes of permutations with a given number of fixed points, Cycle type and descent set in wreath products, Exceedingly deranging!, Lyndon words, permutations and trees., Plethysm and conjugation of quasi-symmetric functions., Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting, On the support of graph Lie algebras, Wheeler graphs: a framework for BWT-based data structures, Foulkes characters, Eulerian idempotents, and an amazing matrix, A note on the Burrows-Wheeler transformation, The peak algebra of the symmetric group revisited., Riffle shuffles, cycles, and descents, Applications of symmetric functions to cycle and increasing subsequence structure after shuffles, Cycle structure of riffle shuffles, Asymptotics of degrees of some \(S_n\)-sub regular representations, Semisimple orbits of Lie algebras and card-shuffling measures on Coxeter groups, 0-Hecke algebra action on the Stanley-Reisner ring of the Boolean algebra, Character formulas and descents for the hyperoctahedral group, On the relationship between combinatorial functions and representation theory, Symmetric functions, noncommutative symmetric functions and quasisymmetric functions. II., On rotated Schur-positive sets, Unimodal permutations and almost-increasing cycles, Schur-concavity for avoidance of increasing subsequences in block-ascending permutations, On the combinatorics of suffix arrays, An extension of the Burrows-Wheeler transform, A new combinatorial approach to sequence comparison, Decomposable compositions, symmetric quasisymmetric functions and equality of ribbon Schur functions, The Eulerian distribution on involutions is indeed unimodal, Spectra of Symmetrized Shuffling Operators, On adding a list of numbers (and other one-dependent determinantal processes), 𝑞-Eulerian polynomials: Excedance number and major index, Sturmian and Episturmian Words, A probabilistic approach to some of Euler’s number theoretic identities

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A decomposition of Solomon's descent algebra
• Witt vectors and the algebra of necklaces
• The action of \(S_ n\) on the components of the Hodge decomposition of Hochschild homology
• The Orlik-Solomon algebra on the partition lattice and the free Lie algebra
• On the eigenvalues of representations of reflection groups and wreath products
• Eulerian numbers, Newcomb's problem and representations of symmetric groups
• A combinatorial interpretation of q-derangement and q-Laguerre numbers
• The major index polynomial for conjugacy classes of permutations
• \(q\)-analogs of the inclusion-exclusion principle and permutations with restricted position
• On some submodules of the action of the symmetric group on the free Lie algebra
• Decompositions of \(S_ n\)-submodules in the free Lie algebra
• Enumeration of permutations with prescribed up-down and inversion sequences
• Signed permutation statistics and cycle type
• Riffle shuffles, cycles, and descents
• Permutations, matrices, and generalized Young tableaux
• On the number of solutions of certain linear Diophantine equations
• Descents of derangements and circular words
• Fonctions symétriques associées à des suites classiques de nombres
• The Analysis of the Characters of the Lie Representations of the General Linear Group
• Longest Increasing and Decreasing Subsequences
• Fonctions symétriques et séries hypergéométriques basiques multivariées
• On Witt's dimension formula for free Lie algebras and a theorem of Klyachko
• On q-Derangement Numbers
• Quotients of Coxeter complexes and 𝑃-partitions
• On the Geometry of Numbers in Elementary Number Theory
• On the Netto Inversion Number of a Sequence
• Ordered structures and partitions
• On Symmetrized Kronecker Powers and the Structure of the Free Lie Ring
• The Free Lie Ring and Lie Representations of the Full Linear Group
• Number of permutations with given descent set and cycle structure