MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

I refer to sequence A211318 in and 'run' is a contiguous sequence of rises or falls in the permutations of n. If the permutations are generated by composition of Standard Young Tableaux with shape according to the partitions of n, then it turns out (why? proof?) that all permutations rho for which rho = T1 . T2 (Robinson-Schensted correspondence, reverse bumping algorithm) have a descent structure that is independent of the left Tableau T1. So, if it doesn't matter what the left tableau is, than we can just as well take it equal to the right tableau, and only count the descent structures of the involutions.

With descent structure, I mean the binary representation of the rises "1" or descents "0" of the permutations. But an even stronger regularity seems to hold for the longest (scattered =not necessarily contiguous) subsequence (LISS) : there all h^2 permutations generated by the h tableaux of a partition of n have the same LISS.

This surely must be known, and I would like to understand the why.

share|cite|improve this question
I am not exactly sure what you're asking, but perhaps you just want Lemma 7.23.1 of Enumerative Combinatorics, vol. 2, which states that the descent set of rho is just the descent set of T2 (and the descent set of rho^{-1} is the descent set of T1). – Richard Stanley May 12 '12 at 1:08

Your Answer


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

Browse other questions tagged or ask your own question.