×

zbMATH — the first resource for mathematics

Permutation statistics and linear extensions of posets. (English) Zbl 0742.05084
The relation between two permutation statistics — the inversion index and the major index — are studied. For a permutation \(\sigma=\sigma_ 1\sigma_ 2\cdots\sigma_ n\), the inversion index is the number of ordered pairs \((i,j)\) such that \(i<j\) and \(\sigma_ i>\sigma_ j\); the major index is the sum of all \(i\) such that \(\sigma_ i>\sigma_{i+1}\). By a theorem of MacMahon these statistics are equidistributed on \(S_ n\), i.e., the number of permutations with a given inversion index coincides with the number of those having the same major index. Foata’s bijection takes \(maj\) to \(inv\) and so justifies this result. The subsets \(U\) of \(S_ n\) for which these statistics are equidistributed are characterized; this extends the previous results of Foata, Schützenberger, and the authors. The characterization is complete when \(U\) is a set of linear extensions of a naturally labeled poset \(P\); in this case \(U\) must be invariant under Foata’s bijection, and \(P\) should be a postorder labeled forest. The intervals in the weak Bruhat order of \(S_ n\) are also studied from the same viewpoint.

MSC:
05E99 Algebraic combinatorics
06A07 Combinatorics of partially ordered sets
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Berge, C., Principles of combinatorics, (1971), Academic Press New York · Zbl 0227.05002
[3] Björner, A.; Wachs, M., Generalized quotients in Coxeter groups, Trans. amer. math. soc., 308, 1-37, (1988) · Zbl 0659.05007
[4] Björner, A.; Wachs, M., q-hook length formulas for forests, J. combin. theory ser. A, 52, 165-187, (1989) · Zbl 0697.06002
[5] Foata, D., On the netto inversion number of a sequence, (), 236-240 · Zbl 0157.03403
[6] Foata, D., Étude algébrique de certains problèmes d’analyse combinatoire et du calcul des probabilitès, Publ. inst. statist univ. Paris, 14, 81-241, (1965) · Zbl 0133.41304
[7] Foata, D.; Schützenberger, M.-P., Major index and inversion numbers of permutations, Math. nachr., 83, 143-159, (1978) · Zbl 0319.05002
[8] Gessel, I., A q-analogue of the exponential formula, Discrete math., 40, 69-80, (1982) · Zbl 0485.05004
[9] Kelly, D., The 3-irreducible partially ordered sets, Canad. J. math., 29, 367-383, (1977) · Zbl 0357.06004
[10] Knuth, D.E., ()
[11] Lothatre, M., Combinatorics on words, ()
[12] Macmahon, P.A.; Macmahon, P.A., The indices of permutations, …, (), 35, 508-549, (1913), Reprinted in · JFM 44.0076.02
[13] Macmahon, P.A.; Macmahon, P.A., Two applications of general theorems in combinatory analysis, (), 556-563, reprinted in · JFM 39.0241.01
[14] Netto, E., ()
[15] Rawlings, D., Inumeration of permutations by descents, idescents, imajor index, and basic components, J. combin. theory A, 36, 1-14, (1984) · Zbl 0527.05005
[16] Simion, R.; Schmidt, F.W., Restricted permutations, European J. combin., 6, 383-406, (1985) · Zbl 0615.05002
[17] Stanley, R.P., Ordered structures and partitions, Mem. amer. math. soc., 119, (1972) · Zbl 0246.05007
[18] Stanley, R.P., ()
[19] Tits, J., Buildings of spherical type and finite BN-pairs, () · Zbl 0295.20047
[20] Trotter, W.T.; Moore, J.I., Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Discrete math., 4, 361-368, (1976)
[21] Yanagimoto, T.; Okamoto, M., Partial orderings of permutations and monotonicity of a rank correlation statistic, Ann. inst. statist. math., 21, 489-506, (1969) · Zbl 0208.44704
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.