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.

  • 3
    $\begingroup$ 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. $\endgroup$ – Alexander Woo Feb 28 '12 at 22:18

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)$.

  • $\begingroup$ 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. $\endgroup$ – William J. Keith Mar 1 '12 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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