MIT Combinatorics Seminar

Alternating Permutations

Richard Stanley (Massachusetts Institute of Technology)

Friday, May 5, 2006   4:30 PM   Building 2 Room 105 


A permutation a_1 a_2 ... a_n of integers is *alternating* if a_1 > a_2 < a_3 > a_4 < ... After a brief survey of this subject we will discuss two new directions of research. (1) The distribution of the length of the longest alternating subsequence of a permutation of 1,2,...,n, analogous to the theory of longest increasing subsequences. (2) The use of symmetric functions to enumerate various classes of alternating permutations of 1,2,...,n, such as those whose inverse is also alternating, or those with a given cycle type.