Counting permutations with given cycle structure and descent set

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

Christophe Reutenauer, Ira M. Gessel

Publication date: 10 August 1994

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

Full work available at URL: https://doi.org/10.1016/0097-3165(93)90095-p

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

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, On two unimodal descent polynomials, 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, Quasisymmetric and Schur expansions of cycle index polynomials, Noncommutative Bell polynomials and the dual immaculate basis, Cyclic sieving, necklaces, and branching rules related to Thrall's problem, The log-concavity of the \(q\)-derangement numbers of type \(B\), Unweighted linear congruences with distinct coordinates and the Varshamov-Tenengolts codes, Block decomposition of permutations and Schur-positivity, Wheeler graphs: a framework for BWT-based data structures, Block numbers of permutations and Schur-positivity, Dual immaculate quasisymmetric functions expand positively into Young quasisymmetric Schur functions, Necessary conditions for Schur-maximality, Foulkes characters, Eulerian idempotents, and an amazing matrix, A note on the Burrows-Wheeler transformation, The peak algebra of the symmetric group revisited., Inverse Lyndon words and inverse Lyndon factorizations of words, 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, Gamma-positivity in combinatorics and geometry, An upper bound on the number of \((132, 213)\)-avoiding cyclic permutations, Central limit theorem for descents in conjugacy classes of \(S_n\), Specializations of colored quasisymmetric functions and Euler-Mahonian identities, Prime power variations of higher \(\mathrm{Lie}_n\) modules, Cyclic permutations: degrees and combinatorial types, Random decompositions of Eulerian statistics, String inference from longest-common-prefix array, Central limit theorem for peaks of a random permutation in a fixed conjugacy class of \(S_n\), r-indexing the eBWT, Computing the original eBWT faster, simpler, and with less memory, Symmetric multisets of permutations, On cyclic Schur-positive sets of permutations, Counting permutations by peaks, descents, and cycle type, Plethystic formulas for permutation enumeration, When a dollar makes a BWT, A central limit theorem for descents and major indices in fixed conjugacy classes of \(S_n\), The alternating BWT: an algorithmic perspective, On the joint distribution of cyclic valleys and excedances over conjugacy classes of \(\mathfrak{S}_n\), Modifying Curtiss' theorem to prove central limit theorems, Labeled binary trees, subarrangements of the Catalan arrangements, and Schur positivity, The Eulerian distribution on the involutions of the hyperoctahedral group is unimodal, 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, Distribution of descents in matchings, A note on Jing and Li's type \(B\) quasisymmetric Schur functions, Exact and asymptotic enumeration of cyclic permutations according to descent set, Unnamed Item, Unnamed Item, $k$-Arrangements, Statistics, and Patterns, A new class of searchable and provably highly compressible string transformations, 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, Counting Linear Extensions of Posets with Determinants of Hook Lengths, Invariant theory for the free left-regular band and a \(q\)-analogue, Asymptotic behavior of some factorizations of random words, A new class of string transformations for compressed text indexing, The Eulerian distribution on the fixed-point free involutions of the hyperoctahedral group, Enumerating two permutation classes by the number of cycles, Cyclic descents, matchings and Schur-positivity, Higher Lie characters and cyclic descent extension on conjugacy classes, 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, The number of cycles with a given descent set, Boolean product polynomials and Schur-positivity, Specializations of colored quasisymmetric functions, Symmetric generating functions and Euler-Stirling statistics on permutations, The Eulerian distribution on \(k\)-colored involutions, 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