Longest alternating subsequences of permutations

By Richard P. Stanley. 2005

87 citations recorded by the source corpus.

The length is(w) of the longest increasing subsequence of a permutation w in the symmetric group Sn has been the object of much investigation. We develop comparable results for the length as(w) of the longest alternating subsequence of w, where a sequence a, b, c, d, . . . is alternating if a > b d < · · · . For instance, the expected value (mean) of as(w) for w ∈ Sn is exactly (4n + 1)/6 if n ≥ 2.

Subfields: Artificial Intelligence, Discrete Mathematics and Combinatorics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/a9f7b1bad0f2d899775c782040a1f095b6079f8c

Citations in the corpus

• A Survey of Alternating Permutations (2009, unknown): “Our source for material in this section is the paper [74].”