Counting Permutations with Even Valleys and Odd Peaks

Thursday, November 13, 2014 - 9:00am - 9:50am
Keller 3-180
Ira Gessel (Brandeis University)
We count permutations in which every valley is in an even position and every peak is in an odd position. Following Dennis Chebikin, we say that a position i of a permutation p is an “alternating descent” if i is odd and a descent of p, or if i is even and an ascent of p, and we define alternating runs to be maximal consecutive subsequences with no alternating descents. Then the permutations to be counted are those with no alternating runs of length 3 or more. We find that the exponential generating function for these permutations is very similar to that for permutations with no increasing runs of length 3 or more, but with x^n/n! replaced by E_n x^n/n!, where E_n is the nth Euler number (with generating function sec x + tan x). The proof uses noncommutative symmetric functions, and also gives related results on alternating descents of permutations due to Chebikin and Remmel.

I will then discuss some other applications of noncommutative symmetric functions in permutation enumeration.
MSC Code: