On the Limiting Distribution for the Length of the Longest Alternating Sequence in a Random Permutation

Harold Widom

Abstract


Recently Richard Stanley initiated a study of the distribution of the length as$_n(w)$ of the longest alternating subsequence in a random permutation $w$ from the symmetric group ${\cal S}_n$. Among other things he found an explicit formula for the generating function (on $n$ and $k$) for Pr$\,$(as$_n(w)\le k)$ and conjectured that the distribution, suitably centered and normalized, tended to a Gaussian with variance 8/45. In this note we present a proof of the conjecture based on the generating function.


Full Text: PDF