Longest alternating subsequences in pattern-restricted permutations
Summary: Inspired by the results of Stanley and Widom concerning the limiting distribution of the lengths of longest alternating subsequences in random permutations, and results of Deutsch, Hildebrand and Wilf on the limiting distribution of the longest increasing subsequence for pattern-restricted permutations, we find the limiting distribution of the longest alternating subsequence for pattern-restricted permutations in which the pattern is any one of the six patterns of length three. Our methodology uses recurrences, generating functions, and complex analysis, and also yields more detailed information. Several ideas for future research are listed.
- Longest alternating subsequences of permutations
- Longest increasing subsequences in pattern-restricted permutations
- Longest alternating subsequences in pattern-restricted \(k\)-ary words
- On the longest \(k\)-alternating subsequence
- scientific article; zbMATH DE number 1998299
- Longest alternating subsequences of \(k\)-ary words
- On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
- Longest monotone subsequences and rare regions of pattern-avoiding permutations
- scientific article; zbMATH DE number 1515819
- Pattern avoiding permutations with a unique longest increasing subsequence
- Longest increasing subsequences in pattern-restricted permutations
- Avoiding patterns and making the best choice
- Strategy-indifferent games of best choice
- Longest monotone subsequences and rare regions of pattern-avoiding permutations
- Pattern-avoiding alternating words
- Local extrema in random permutations and the structure of longest alternating subsequences
- Longest alternating subsequences in pattern-restricted \(k\)-ary words
- Small Longest Tandem Scattered Subsequences
- On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
- Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three
- Mean and variance of the longest alternating subsequence in a random separable permutation
- Longest subsequence for certain repeated up/down patterns in random permutations avoiding a pattern of length three
- Longest alternating subsequences of permutations
This page was built for publication: Longest alternating subsequences in pattern-restricted permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2372878)
