Local extrema in random permutations and the structure of longest alternating subsequences
Let $\textbf{as}_n$ denote the length of a longest alternating subsequence in a uniformly random permutation of order $n$. Stanley studied the distribution of $\textbf{as}_n$ using algebraic methods, and showed in particular that $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ and $\textrm{Var}(\textbf{as}_n...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2011-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2956/pdf |