MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It appears from computation to be the case (and would prove at least one clause of a conjecture advanced by Bruce Sagan and collaborators in a recent preprint) that in some pattern avoidance classes of permutations, the distribution of the major index is symmetric among permutations with a given descent number. For instance, $$\sum_{S_6(1234)} q^{maj(\sigma)}t^{des(\sigma)} = \dots + (10 q^6 + 35 q^7 + 66 q^8 + 80 q^9 + 66 q^{10} + 35 q^{11} + 10 q^{12}) t^3 + \dots.$$

As you can see, the coefficient of $t^3$ is a symmetric polynomial.

This is not the case for all avoidance classes: for instance, $$\sum_{S_6(2134)} q^{maj(\sigma)}t^{des(\sigma)} = \dots + (4 q^6 + 21 q^7 + 42 q^8 + 61 q^9 + 56 q^{10} + 35 q^{11} + 10 q^{12}) t^3 + \dots.$$

Before I start hammering at this, I was wondering if this was known to be the case for any particular avoidance classes, and if so, which. Since I have not even found any papers that seem to deal with the subject, pointers to one you know of would also be gratefully received.

share|cite|improve this question
My vague impression is that there are papers on permutation statistics for pattern avoidance classes, but I don't know specific references. Sadly, your best bet may be to show up at Permutation Patterns 2012 (in Glasgow in June) and ask around. – Alexander Woo Feb 28 '12 at 22:18
up vote 11 down vote accepted

Let $w=a_1 a_2\cdots a_n\in S_n$. Set $w' =n+1-a_n,n+1-a_{n-1},\dots,n+1-a_1$. Then (1) $\mathrm{des}(w)=\mathrm{des}(w')$, (2) $\mathrm{maj}(w)+\mathrm{maj}(w')=dn$, where $d=\mathrm{des}(w)$, and (3) $\mathrm{is}(w)=\mathrm{is}(w')$, where $\mathrm{is}(w)$ denotes the length of the longest increasing subsequence of $w$. This implies the suggested symmetry property for $S_n(12\cdots p)$. Since the map $w\mapsto w'$ also preserves the length of the longest decreasing subsequence (in fact, it preserves the RSK insertion tableau), the symmetry property also holds for $S_n(12\cdots p, q\cdots 21)$.

share|cite|improve this answer
Thanks Richard. Your argument also proves the property for any other class preserved by reverse-complement, such as $S_n(2143)$, since that's the purpose of (3) and the properties (1) and (2) hold generally. Also seems to hold for a few other singleton classes, but given the discussion so far I think I can attack it with confidence and at least know I'm not reinventing the wheel. – William J. Keith Mar 1 '12 at 11:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.