# zbMATH — the first resource for mathematics

Counting permutations with given cycle structure and descent set. (English) Zbl 0793.05004
From the authors’ introduction: Let $$\sigma$$ be a permutation in the symmetric group $$S_ n$$. If $$\sigma$$ has $$n_ i$$ cycles of length $$i$$ for each $$i$$, then we say that the cycle structure of $$\sigma$$ is the partition $$1^{n_ 1}2^{n_ 2}\cdots$$. The descent set of $$\sigma$$ is the set $$\{i\mid 1 \leq i\leq n-1$$ and $$\sigma(i)>\sigma(i+ 1)\}$$. The purpose of this paper is to count permutations in $$S_ n$$ with a given cycle structure and a given descent set. Our main result (Theorem 2.1) asserts that the number of these permutations can be expressed as a scalar produt of two symmetric functions, one associated with the cycle structure and the other with the descent set. Both of these symmetric functions can be interpreted as characteristics of certain representations of the symmetric group.

##### MSC:
 05A15 Exact enumeration problems, generating functions 05A05 Permutations, words, matrices 05E05 Symmetric functions and generalizations
Full Text:
##### References:
  Andrews, G.E, The theory of partitions, () · Zbl 0155.09302  Barcelo, H; Bergeron, N, The orlik-Solomon algebra on the partition lattice and the free Lie algebra, J. combin. theory ser. A, 55, 80-92, (1990) · Zbl 0709.17004  Barcelo, H; Sundaram, S, On some submodules of the action of the symmetric group on the free Lie algebra, J. algebra, 154, 12-26, (1993) · Zbl 0851.17006  Bergeron, F; Bergeron, N; Garsia, A.M, Idempotents for the free Lie algebra and q-enumeration, (), 166-190 · Zbl 0721.17006  Blessenohl, D; Laue, H, On Witt’s dimension formula for free Lie algebras and a theorem of klyachko, Bull. austral. math. soc., 40, 49-57, (1989) · Zbl 0664.17003  Blessenohl, D; Laue, H, Symmetric groups and free Lie algebras, (), 201-208 · Zbl 0742.17010  Brandt, A.J, The free Lie ring and Lie representations of the full linear group, Trans. amer. math. soc., 56, 528-536, (1944) · Zbl 0063.00597  Chen, W.Y.C; Rota, G.-C, q-analogs of the inclusion-exclusion principle and permutations with restricted position, Discrete math., 104, 7-22, (1992) · Zbl 0806.05010  Davis, R.L, A special formula for the Lie character, Canad. J. math., 10, 33-38, (1958)  Désarménien, J, Fonctions symétriques associées à des suites classiques des nombres, Ann. sci. école norm. sup., 16, 271-304, (1983) · Zbl 0525.05006  Désarménien, J, Une autre interprétation du nombre de dérangements, (), 11-16  Désarménien, J, Étude modulo n des statistiques mahoniennes, (), 27-35  Désarménien, J; Foata, D, Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. soc. math. France, 113, 3-22, (1985) · Zbl 0644.05005  Désarménien, J; Wachs, M, Descentes sur LES dérangements et mots circulaires, (), 13-21, 361/S19  Dress, A.W.M; Siebeneicher, C, Ein lemma über perlenketten, (), 41-55  Dress, A.W.M; Siebeneicher, C, On the number of solutions of certain linear Diophantine equations, Hokkaido math. J., 19, 385-401, (1990) · Zbl 0722.05014  Dress, A; Siebeneicher, C, Zur abzählung periodischer worte, (), 19-31  Foata, D, On the netto inversion number of a sequence, (), 236-240 · Zbl 0157.03403  Foulkes, H.O, The analysis of the characters of the Lie representations of the general linear group, (), 497-501 · Zbl 0093.03303  Foulkes, H.O, Enumerations of permutations with prescribed up-down and inversion sequences, Discrete math., 15, 235-252, (1976) · Zbl 0338.05002  Foulkes, H.O, Eulerian numbers, Newcomb’s problem and representations of symmetric groups, Discrete math., 30, 3-49, (1980) · Zbl 0445.05008  Garsia, A.M, Combinatorics of the free Lie algebra and the symmetric group, (), 309-382 · Zbl 0178.38601  Garsia, A.M; Remmel, J, A combinatorial interpretation of q-derangement and q-Laguerre numbers, Eur. J. combin., 1, 47-59, (1980) · Zbl 0462.05012  Garsia, A.M; Reutenauer, C, A decomposition of Solomon’s descent algebra, Adv. math., 77, 189-262, (1989) · Zbl 0716.20006  Gessel, I, Counting permutations by descents, greater index, and cycle structure, (1981), unpublished manuscript  Gessel, I, Multipartite P-partitions and inner product of skew Schur functions, Contemp. math., 34, 289-301, (1984)  Hanlon, P, The action of Sn on the components of the Hodge decomposition of Hochschild homology, Michigan math. J., 37, 105-124, (1990) · Zbl 0701.16010  Joyal, A, Foncteurs analytiques et espèces de structures, (), 126-159  Kerber, A; Thürlings, K.-J, Symmetrieklassen von funktionen und ihre abzählungstheorie (teil II: hinzunahme darstellungstheoretischer begriffsbildungen), () · Zbl 0529.05005  Klyachko, A.A, Lie elements in the tensor algebra, Siberian math. J., 15, No. 6, 1296-1304, (1974) · Zbl 0315.15015  Knuth, D.E, Permutations, matrices, and generalized Young tableaux, Pacific J. math., 34, 709-727, (1970) · Zbl 0199.31901  Kraskiewicz, W; Weyman, J, Algebra of invariants and the action of a Coxeter element, (1987), Math. Inst. Copernicus Univ. Chopina Torun  Lothaire, M, Combinatorics on words, (1983), Addison-Wesley Reading, MA · Zbl 0514.20045  Lascoux, A; Schützenberger, M.-P, Le monoïde plaxique, (), 129-156 · Zbl 0517.20036  Macdonald, I.G, Symmetric functions and Hall polynomials, (1979), Clarendon Oxford · Zbl 0487.20007  MacMahon, P.A, Combinatory analysis, (1960), Chelsea New York, [First edition in two vols. by Cambridge Univ. Press, 1915, 1916] · Zbl 0101.25102  Mallows, C.L, Problems S 14∗, Amer. math. monthly, 86, 503, (1979)  Metropolis, N; Rota, G.-C, Witt vectors and the algebra of necklaces, Adv. math., 50, 95-125, (1983) · Zbl 0545.05009  Metropolis, N; Rota, G.-C, The cyclotomic identity, Contemp. math., 34, 19-24, (1984)  Reiner, V.S, Quotients of Coxeter complexes and P-partitions, () · Zbl 0751.06002  \scV. S. Reiner, Signed permutation statistics and cycle type, preprint. · Zbl 0793.05006  Reutenauer, C, Theorem of Poincaré-Birkhoff-Witt, logarithm and representation of the symmetric group whose order are the Stirling numbers, (), 267-284  Reutenauer, C, Number of permutations with given descent set and cycle structure, (), 99-110  Schensted, C, Longest increasing and decreasing subsequences, Canad. J. math., 13, 179-191, (1961) · Zbl 0097.25202  Stanley, R.P, Ordered structures and partitions, () · Zbl 0246.05007  Stanley, R.P, ()  Stembridge, J.R, On the eigenvalues of representations of reflection groups and wreath products, Pacific J. math., 140, 353-396, (1989) · Zbl 0641.20011  Strehl, V, Symmetric Eulerian distributions for involutions, (), 12  Sundaram, S, Decompositions of some S_n-modules arising in the free Lie algebra, J. algebra, 154, 507-558, (1993) · Zbl 0851.17005  Thrall, R.M, On symmetrized Kronecker powers and the structure of the free Lie ring, Amer. J. math., 64, 371-388, (1942) · Zbl 0061.04201  Wachs, M.L, On q-derangement numbers, (), 273-278 · Zbl 0669.05006  Wachs, M.L, The major index polynomial for conjugacy classes of permutations, Discrete math., 91, 283-293, (1991) · Zbl 0756.05002  \scM. L. Wachs, Descents sets of derangements, preprint. · Zbl 1186.05004  Witt, E, Treue darstellung liescher ringe, J. reine angew. math., 177, 152-160, (1937) · JFM 63.0089.02  \scP. Diaconis, M. McGrath, J. Pitman, Riffle shuffles, cycles, and descents, preprint. · Zbl 0828.05003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.