Longest alternating subsequences of permutations
From MaRDI portal
Publication:841561
DOI10.1307/MMJ/1220879431zbMATH Open1247.05016arXivmath/0511419OpenAlexW2087114314MaRDI QIDQ841561FDOQ841561
Authors: Richard P. Stanley 
Publication date: 17 September 2009
Published in: Michigan Mathematical Journal (Search for Journal in Brave)
Abstract: The length is(w) of the longest increasing subsequence of a permutation w in the symmetric group S_n 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<c>d<.... For instance, the expected value (mean) of as(w) for w in S_n is exactly (4n+1)/6 if n>1.
Full work available at URL: https://arxiv.org/abs/math/0511419
Recommendations
- On the limiting distribution for the length of the longest alternating sequence in a random permutation
- Local extrema in random permutations and the structure of longest alternating subsequences
- A probabilistic approach to the asymptotics of the length of the longest alternating subsequence
- Longest alternating subsequences of \(k\)-ary words
- Longest alternating subsequences in pattern-restricted permutations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Asymptotics of multivariate sequences. I: Smooth points of the singular variety
- On the distribution of the length of the longest increasing subsequence of random permutations
- Symmetric functions and P-recursiveness
- Title not available (Why is that?)
- Central and local limit theorems applied to asymptotic enumeration
- On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
- Asymptotic values for degrees associated with strips of Young diagrams
- Excluded permutation matrices and the Stanley-Wilf conjecture
- A variational problem for random Young tableaux
- Title not available (Why is that?)
- Central and local limit theorems applied to asymptotic enumeration. II: Multivariate generating functions
- On the limiting distribution for the length of the longest alternating sequence in a random permutation
Cited In (34)
- Online Selection of Alternating Subsequences from a Random Sample
- Title not available (Why is that?)
- Longest monotone subsequences and rare regions of pattern-avoiding permutations
- Optimal Online Selection of an Alternating Subsequence: A Central Limit Theorem
- Context-free grammars for several polynomials associated with Eulerian polynomials
- \(q\)-log-convexity from linear transformations and polynomials with only real zeros
- The peak statistics on simsun permutations
- Counting permutations by runs
- Several variants of the Dumont differential system and permutation statistics
- Martingales and descent statistics
- Enumeration of permutations by number of alternating runs
- Average length of the longest \(k\)-alternating subsequence
- An explicit formula for the number of permutations with a given number of alternating runs
- Counting permutations by simsun successions
- Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three
- Eulerian polynomials and descent statistics
- Plethystic formulas for permutation enumeration
- Sharp large deviations and concentration inequalities for the number of descents in a random permutation
- Counting permutations by their alternating runs
- Generating functions of permutations with respect to their alternating runs
- On the longest \(k\)-alternating subsequence
- A central limit theorem for temporally nonhomogenous Markov chains with applications to dynamic programming
- Title not available (Why is that?)
- On the Number of Reflexive and Shared Nearest Neighbor Pairs in One-Dimensional Uniform Data
- Two-sided permutation statistics via symmetric functions
- Counting signed permutations by their alternating runs
- Eulerian pairs and Eulerian recurrence systems
- A grammatical calculus for peaks and runs of permutations
- Homomorphisms on noncommutative symmetric functions and permutation enumeration
- Longest alternating subsequences in pattern-restricted permutations
- Longest alternating subsequences of \(k\)-ary words
- David-Barton type identities and alternating run polynomials
- Descent-inversion statistics in riffle shuffles
- Some combinatorial arrays related to the Lotka-Volterra system
This page was built for publication: Longest alternating subsequences of permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q841561)
