×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrews, G.E, The theory of partitions, () · Zbl 0155.09302
[2] 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
[3] 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
[4] Bergeron, F; Bergeron, N; Garsia, A.M, Idempotents for the free Lie algebra and q-enumeration, (), 166-190 · Zbl 0721.17006
[5] 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
[6] Blessenohl, D; Laue, H, Symmetric groups and free Lie algebras, (), 201-208 · Zbl 0742.17010
[7] 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
[8] 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
[9] Davis, R.L, A special formula for the Lie character, Canad. J. math., 10, 33-38, (1958)
[10] 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
[11] Désarménien, J, Une autre interprétation du nombre de dérangements, (), 11-16
[12] Désarménien, J, Étude modulo n des statistiques mahoniennes, (), 27-35
[13] 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
[14] Désarménien, J; Wachs, M, Descentes sur LES dérangements et mots circulaires, (), 13-21, 361/S19
[15] Dress, A.W.M; Siebeneicher, C, Ein lemma über perlenketten, (), 41-55
[16] 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
[17] Dress, A; Siebeneicher, C, Zur abzählung periodischer worte, (), 19-31
[18] Foata, D, On the netto inversion number of a sequence, (), 236-240 · Zbl 0157.03403
[19] Foulkes, H.O, The analysis of the characters of the Lie representations of the general linear group, (), 497-501 · Zbl 0093.03303
[20] Foulkes, H.O, Enumerations of permutations with prescribed up-down and inversion sequences, Discrete math., 15, 235-252, (1976) · Zbl 0338.05002
[21] Foulkes, H.O, Eulerian numbers, Newcomb’s problem and representations of symmetric groups, Discrete math., 30, 3-49, (1980) · Zbl 0445.05008
[22] Garsia, A.M, Combinatorics of the free Lie algebra and the symmetric group, (), 309-382 · Zbl 0178.38601
[23] 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
[24] Garsia, A.M; Reutenauer, C, A decomposition of Solomon’s descent algebra, Adv. math., 77, 189-262, (1989) · Zbl 0716.20006
[25] Gessel, I, Counting permutations by descents, greater index, and cycle structure, (1981), unpublished manuscript
[26] Gessel, I, Multipartite P-partitions and inner product of skew Schur functions, Contemp. math., 34, 289-301, (1984)
[27] 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
[28] Joyal, A, Foncteurs analytiques et espèces de structures, (), 126-159
[29] Kerber, A; Thürlings, K.-J, Symmetrieklassen von funktionen und ihre abzählungstheorie (teil II: hinzunahme darstellungstheoretischer begriffsbildungen), () · Zbl 0529.05005
[30] Klyachko, A.A, Lie elements in the tensor algebra, Siberian math. J., 15, No. 6, 1296-1304, (1974) · Zbl 0315.15015
[31] Knuth, D.E, Permutations, matrices, and generalized Young tableaux, Pacific J. math., 34, 709-727, (1970) · Zbl 0199.31901
[32] Kraskiewicz, W; Weyman, J, Algebra of invariants and the action of a Coxeter element, (1987), Math. Inst. Copernicus Univ. Chopina Torun
[33] Lothaire, M, Combinatorics on words, (1983), Addison-Wesley Reading, MA · Zbl 0514.20045
[34] Lascoux, A; Schützenberger, M.-P, Le monoïde plaxique, (), 129-156 · Zbl 0517.20036
[35] Macdonald, I.G, Symmetric functions and Hall polynomials, (1979), Clarendon Oxford · Zbl 0487.20007
[36] MacMahon, P.A, Combinatory analysis, (1960), Chelsea New York, [First edition in two vols. by Cambridge Univ. Press, 1915, 1916] · Zbl 0101.25102
[37] Mallows, C.L, Problems S 14∗, Amer. math. monthly, 86, 503, (1979)
[38] Metropolis, N; Rota, G.-C, Witt vectors and the algebra of necklaces, Adv. math., 50, 95-125, (1983) · Zbl 0545.05009
[39] Metropolis, N; Rota, G.-C, The cyclotomic identity, Contemp. math., 34, 19-24, (1984)
[40] Reiner, V.S, Quotients of Coxeter complexes and P-partitions, () · Zbl 0751.06002
[41] \scV. S. Reiner, Signed permutation statistics and cycle type, preprint. · Zbl 0793.05006
[42] Reutenauer, C, Theorem of Poincaré-Birkhoff-Witt, logarithm and representation of the symmetric group whose order are the Stirling numbers, (), 267-284
[43] Reutenauer, C, Number of permutations with given descent set and cycle structure, (), 99-110
[44] Schensted, C, Longest increasing and decreasing subsequences, Canad. J. math., 13, 179-191, (1961) · Zbl 0097.25202
[45] Stanley, R.P, Ordered structures and partitions, () · Zbl 0246.05007
[46] Stanley, R.P, ()
[47] Stembridge, J.R, On the eigenvalues of representations of reflection groups and wreath products, Pacific J. math., 140, 353-396, (1989) · Zbl 0641.20011
[48] Strehl, V, Symmetric Eulerian distributions for involutions, (), 12
[49] Sundaram, S, Decompositions of some S_n-modules arising in the free Lie algebra, J. algebra, 154, 507-558, (1993) · Zbl 0851.17005
[50] 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
[51] Wachs, M.L, On q-derangement numbers, (), 273-278 · Zbl 0669.05006
[52] Wachs, M.L, The major index polynomial for conjugacy classes of permutations, Discrete math., 91, 283-293, (1991) · Zbl 0756.05002
[53] \scM. L. Wachs, Descents sets of derangements, preprint. · Zbl 1186.05004
[54] Witt, E, Treue darstellung liescher ringe, J. reine angew. math., 177, 152-160, (1937) · JFM 63.0089.02
[55] \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.