A Survey of Alternating Permutations

A permutation $a_1 a_2 \cdots a_n$ of $1, 2, \dots, n$ is \emph{alternating} if $a_1 > a_2 < a_3 > a_4 < a_5 > \cdots$. If $E_n$ is the number of alternating permutations of $1, 2, \dots, n$, then $$ \sum_{n\geq 0} E_n \frac{x^n}{n!} = \sec x + \tan x. $$ We will discuss several aspects of the theory of alternating permutations. Some occurences of the numbers $E_n$, such as counting orbits of group actions and volumes of polytopes, will be surveyed. The behavior of the length of the longest alternating subsequence of a random permutation will be analyzed, in analogy to the length of the longest increasing subsequence. We will also explain how various classes of alternating permutations, such as those that are also fixed-point free involutions, can by counted using umbral techniques arising from a certain representation of the symmetric group $S_n$ whose dimension is $E_n$.

Richard Stanley, Massachusetts Institute of Technology

Renew SIAM · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube