# 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
##### Keywords:
permutation statistics; inversion index; major index
Full Text:
##### References:
  Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0286.68029  Berge, C., Principles of combinatorics, (1971), Academic Press New York · Zbl 0227.05002  Björner, A.; Wachs, M., Generalized quotients in Coxeter groups, Trans. amer. math. soc., 308, 1-37, (1988) · Zbl 0659.05007  Björner, A.; Wachs, M., q-hook length formulas for forests, J. combin. theory ser. A, 52, 165-187, (1989) · Zbl 0697.06002  Foata, D., On the netto inversion number of a sequence, (), 236-240 · Zbl 0157.03403  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  Foata, D.; Schützenberger, M.-P., Major index and inversion numbers of permutations, Math. nachr., 83, 143-159, (1978) · Zbl 0319.05002  Gessel, I., A q-analogue of the exponential formula, Discrete math., 40, 69-80, (1982) · Zbl 0485.05004  Kelly, D., The 3-irreducible partially ordered sets, Canad. J. math., 29, 367-383, (1977) · Zbl 0357.06004  Knuth, D.E., ()  Lothatre, M., Combinatorics on words, ()  Macmahon, P.A.; Macmahon, P.A., The indices of permutations, …, (), 35, 508-549, (1913), Reprinted in · JFM 44.0076.02  Macmahon, P.A.; Macmahon, P.A., Two applications of general theorems in combinatory analysis, (), 556-563, reprinted in · JFM 39.0241.01  Netto, E., ()  Rawlings, D., Inumeration of permutations by descents, idescents, imajor index, and basic components, J. combin. theory A, 36, 1-14, (1984) · Zbl 0527.05005  Simion, R.; Schmidt, F.W., Restricted permutations, European J. combin., 6, 383-406, (1985) · Zbl 0615.05002  Stanley, R.P., Ordered structures and partitions, Mem. amer. math. soc., 119, (1972) · Zbl 0246.05007  Stanley, R.P., ()  Tits, J., Buildings of spherical type and finite BN-pairs, () · Zbl 0295.20047  Trotter, W.T.; Moore, J.I., Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Discrete math., 4, 361-368, (1976)  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.