×

Enumerating \(S_n\) by associated transpositions and linear extensions of finite posets. (English) Zbl 1187.05008

Summary: We define a family of statistics over the symmetric group \(S_n\) indexed by subsets of the transpositions, and we study the corresponding generating functions. We show that they have many interesting combinatorial properties. In particular we prove that any poset of size \(n\) corresponds to a subset of transpositions of \(S_n\), and that the generating function of the corresponding statistic includes partial linear extensions of such a poset. We prove equidistribution results, and we explicitly compute the associated generating functions for several classes of subsets.

MSC:

05A15 Exact enumeration problems, generating functions
05E15 Combinatorial aspects of groups and algebras (MSC2010)
20B30 Symmetric groups
06A06 Partial orders, general
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adin, R. M.; Brenti, F.; Roichman, Y., Descent numbers and major indices for the hyperoctahedral group, Adv. Appl. Math., 27, 210-224 (2001) · Zbl 0995.05008
[2] Adin, R.; Brenti, F.; Roichman, Y., A unified construction of Coxeter group representations (I), Adv. in Appl. Math., 37, 31-67 (2006) · Zbl 1150.20002
[3] Adin, R.; Brenti, F.; Roichman, Y., Equi-distribution over descent classes of the hyperoctahedral group, J. Combin. Theory Ser. A, 113, 917-933 (2006) · Zbl 1095.05001
[4] Adin, R. M.; Roichman, Y., The flag major index and group actions on polynomial rings, European J. Combin., 22, 431-446 (2001) · Zbl 1058.20031
[5] Anderson, I., Combinatorics of Finite Sets (2002), Dover Publ.: Dover Publ. New York · Zbl 0995.05001
[6] Bender, E. A., Asymptotic methods in enumeration, SIAM Rev., 16, 485-515 (1974) · Zbl 0294.05002
[7] Bender, E. A., Errata: Asymptotic methods in enumeration, SIAM Rev.. SIAM Rev., SIAM Rev., 18, 292-515 (1976) · Zbl 0321.05007
[8] Bennett, C. D.; Blok, R. J., Partial orders generalizing the weak order on Coxeter groups, J. Combin Theory Ser. A, 102, 331-346 (2003) · Zbl 1027.06003
[9] Bennett, C. D.; Evani, L.; Grabiner, D., A simple definitions for the universal Grassmannian order, J. Combin Theory Ser. A, 102, 347-366 (2003) · Zbl 1018.05107
[10] Biagioli, R., Major and descent statistics for the even-signed permutation group, Adv. Appl. Math., 31, 163-179 (2003) · Zbl 1020.05006
[11] Björner, A., Orderings of Coxeter groups, Contemp. Math., 34, 175-195 (1984)
[12] Björner, A.; Brenti, F., (Combinatorics of Coxeter groups. Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231 (2005), Springer-Verlag: Springer-Verlag New York) · Zbl 1110.05001
[13] Björner, A.; Wachs, M. L., Generalized quotients in Coxeter groups, Trans. Amer. Math. Soc., 308, 1-37 (1988) · Zbl 0659.05007
[14] Björner, A.; Wachs, M. L., Permutation statistics and linear extensions of posets, J. Combin. Theory Ser. A, 58, 85-114 (1991) · Zbl 0742.05084
[15] Bóna, M., A simplicial complex of 2-stack sortable permutations, Adv. Appl. Math., 29, 499-508 (2002) · Zbl 1014.05001
[16] Bóna, M.; Ehrenborg, R., A combinatorial proof of the log-concavity of the numbers of permutations with \(k\) runs, J. Combin. Theory Ser. A, 90, 293-303 (2000) · Zbl 0951.05002
[17] Bourbaki, N., Groupes et Algèbres de Lie, (Éléments de mathématique, Fascicule XXXIV (1968), Hermann: Hermann Paris), (Chapitres IV-VI, reprinted in Masson, Paris 1981) · Zbl 0483.22001
[18] Brenti, F., Unimodal polynomials arising from symmetric functions, Proc. Amer. Math. Soc., 108, 1133-1141 (1990) · Zbl 0701.05003
[19] Brenti, F., Log-concave and unimodal sequences in algebra, combinatorics, and geometry: An update, Contemp. Math., 178, 71-89 (1994) · Zbl 0813.05007
[20] Brenti, F., \(q\)-Eulerian polynomials arising from coxeter groups, European J. Combin., 15, 417-441 (1994) · Zbl 0809.05012
[21] Brenti, F., Hilbert polynomials in combinatorics, J. Algebraic Combin., 7, 127-156 (1998) · Zbl 0901.05093
[22] Brown, K. S., Buildings (1989), Springer-Verlag: Springer-Verlag New York · Zbl 0715.20017
[23] Chow, C.-O., On the Eulerian polynomials of type \(D\), European J. Combin., 24, 391-408 (2003) · Zbl 1033.05003
[24] Comtet, L., Advanced Combinatorics (1974), D. Reidel: D. Reidel Dordrecht
[25] A. Conflitti, Enumeration by associated reflections on Coxeter systems, J. Algebra (in press); A. Conflitti, Enumeration by associated reflections on Coxeter systems, J. Algebra (in press) · Zbl 1167.05052
[26] Deodhar, V. V., Some characterizations of Coxeter groups, Enseign. Math., 32, 111-120 (1986) · Zbl 0611.20030
[27] Ehrenborg, R.; Levin, M.; Readdy, M. A., A probabilistic approach to the descent statistic, J. Combin. Theory Ser. A, 98, 150-162 (2002) · Zbl 1005.05005
[28] Ehrenborg, R.; Steingrímsson, E., The excedence set of a permutation, Adv. Appl. Math., 24, 284-299 (2000) · Zbl 0957.05006
[29] Ehrenborg, R.; Steingrímsson, E., Yet another triangle for the Genocchi numbers, European J. Combin., 21, 593-600 (2000) · Zbl 0965.05009
[30] Foata, D., On the Netto inversion number of a sequence, Proc. Amer. Math. Soc., 19, 236-240 (1968) · Zbl 0157.03403
[31] Foata, D.; Schützenberger, M.-P., Major index and inversion number of permutations, Math. Nachr., 83, 143-159 (1978) · Zbl 0319.05002
[32] Foata, D.; Schützenberger, M.-P., Théorie Géométrique des Polynômes Eulériens (1970), Springer-Verlag: Springer-Verlag Berlin · Zbl 0214.26202
[33] Fu, J. C.; Lou, W. Y.W.; Wang, Y.-J., On the exact distribution of Eulerian and Simon Newcomb numbers associated with random permutations, Statist. Probab. Lett., 42, 115-125 (1999) · Zbl 1057.62503
[34] Gasharov, V., On the Neggers-Stanley conjecture and the Eulerian polynomials, J. Combin. Theory Ser. A, 82, 134-146 (1998) · Zbl 0911.05005
[35] Gasharov, V., Factoring the Poincaré polynomials for the Bruhat order on \(S_n\), J. Combin. Theory Ser. A, 83, 159-164 (1998) · Zbl 0935.05087
[36] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1994), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Reading, MA · Zbl 0836.00001
[37] Greene, C.; Kleitman, D. J., Proofs techniques in the theory of finite sets, (Studies in Combinatorics. Studies in Combinatorics, MAA Studies in Mathematics, vol. 17 (1978), The Mathematical Association of America), 22-79
[38] Harris, B.; Park, C. J., A generalization of the Eulerian numbers with a probabilistic application, Statist. Probab. Lett., 20, 37-47 (1994) · Zbl 0801.60013
[39] Hiller, H., Geometry of Coxeter Groups (1982), Pitman (Advanced Publishing Program): Pitman (Advanced Publishing Program) Boston, London, Melbourne · Zbl 0483.57002
[40] Hofri, M., Probabilistic Analysis of Algorithms (1987), Springer-Verlag: Springer-Verlag New York
[41] Hoggar, S. G., Chromatic polynomials and logarithmic concavity, J. Combinatorial Theory Ser. B, 16, 248-254 (1974) · Zbl 0268.05104
[42] Humphreys, J. H., Reflection Groups and Coxeter Groups (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0725.20028
[43] MacMahon, P. A., The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage objects, Amer. J. Math., 35, 281-322 (1913) · JFM 44.0076.02
[44] MacMahon, P. A., Combinatory Analysis (1984), Chelsea Publishing Company: Chelsea Publishing Company New York · JFM 45.1271.01
[45] Nicolas, J.-L., Propriétés arithmétiques de certains nombres eulériens, Colloq. Math., 65, 307-320 (1993) · Zbl 0822.11019
[46] Reiner, V., The distribution of descent and length in a Coxeter group, Electron. J. Combin., 2 (1995), Research paper 25, 20 pp.
[47] Solomon, L., Presenting the symmetric group with transpositions, J. Algebra, 168, 521-524 (1994) · Zbl 0830.20005
[48] Stanley, R. P., Log-concave and unimodal sequences in algebra, combinatorics and geometry, (Graph Theory and Its Applications: East and West. Graph Theory and Its Applications: East and West, Annals of the New York Academy of Sciences, vol. 576 (1989)), 500-534 · Zbl 0792.05008
[49] Stanley, R. P., Enumerative Combinatorics Vol. 1 (1997), Cambridge University Press · Zbl 0889.05001
[50] Stembridge, J. R., Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Discrete Math., 99, 307-320 (1992) · Zbl 0761.05097
[51] Suter, R., Coxetergruppen, Elem. Math., 52, 12-22 (1997), (in German) · Zbl 0877.20028
[52] Tanimoto, S., An operator on permutations and its applications to Eulerian numbers, European J. Combin., 22, 569-576 (2001) · Zbl 0986.05005
[53] Tanimoto, S., A study of Eulerian numbers by means of an operator on permutations, European J. Combin., 24, 33-43 (2003) · Zbl 1014.05007
[54] Winkel, R., A combinatorial derivation of the Poincaré polynomials of the finite irreducible Coxeter groups, Discrete Math., 239, 83-99 (2001) · Zbl 1009.20043
[55] Worpitzky, J., Studien über die Bernoullischen und Eulerschen Zahlen, J. Reine Angew. Math., 94, 203-232 (1883) · JFM 15.0201.01
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.