2015-06-29Alternating PermutationsRichard P. Stanley (MIT)
Lecture 1. (June 29) Euler numbers and André's theorem
The number of alternating permutations of 1, 2, ..., n is denoted En and is called an Euler number. The first theorem on alternating permutations is the generating function
∑n≥0 En xn / n! = tan(x) + sec(x)
due to D. André in 1879. Some other combinatorial objects are also counted by the Euler numbers.
2015-06-30Alternating PermutationsRichard P. Stanley (MIT)
Lecture 2. (June 30) Convex polytopes and alternating permutations
There are two interesting convex polytopes whose volume is En / n!. One of them is given by xi ≥ 0 (1 ≤ i ≤ n) and xi + xi+1 ≤ 1 (1 ≤ i ≤ n-1). They fit into a more general context of order polytopes and chain polytopes of posets.
2015-07-01Alternating PermutationsRichard P. Stanley (MIT)
Lecture 3. (July 1) Longest alternating subsequences
What can one say about the length of the longest alternating subsequence of a random permutation? This theory is analogous but simpler than the better-known theory of the longest increasing subsequence of a random permutation. For example, if n>1 then the expected length of the longest alternating subsequence of a random permutation of 1, 2, ..., n is exactly (4n+1)/6.
2015-07-02Alternating PermutationsRichard P. Stanley (MIT)
Lecture 4. (July 2) A symmetric group character related to alternating permutations
H. O. Foulkes defined a certain character χ of the symmetric group Sn whose values χ(w) are either 0 or ±Ek for some 1 ≤ k ≤ n (depending on w). This character allows us to enumerate certain classes of alternating permutations using representation theory. For instance, if p is prime then the number of alternating permutations in Sp that are also p-cycles is equal to
(Ep - (-1)(p-1)/2) / p.
No elementary proof is known.
2015-07-03Alternating PermutationsRichard P. Stanley (MIT)
Lecture 5. (July 3) The cd-index of the symmetric group
The cd-index of Sn is a noncommutative polynomial in the indeterminates c and d that encodes a lot of combinatorial information. The number of terms in this polynomial is En, and there are interesting connections with alternating permutations.