Permutation statistics and linear extensions of posets (Q1177948): Difference between revisions

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.