Longest alternating subsequences of permutations
From MaRDI portal
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.
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
- scientific article; zbMATH DE number 3630761 (Why is no real title available?)
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 1033192 (Why is no real title available?)
- scientific article; zbMATH DE number 1033382 (Why is no real title available?)
- A variational problem for random Young tableaux
- Asymptotic values for degrees associated with strips of Young diagrams
- Asymptotics of multivariate sequences. I: Smooth points of the singular variety
- Central and local limit theorems applied to asymptotic enumeration
- Central and local limit theorems applied to asymptotic enumeration. II: Multivariate generating functions
- Excluded permutation matrices and the Stanley-Wilf conjecture
- On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
- On the distribution of the length of the longest increasing subsequence of random permutations
- On the limiting distribution for the length of the longest alternating sequence in a random permutation
- Symmetric functions and P-recursiveness
Cited in
(39)- Martingales and descent statistics
- Enumeration of permutations by number of alternating runs
- A note on a permutation statistic
- On the longest \(k\)-alternating subsequence
- Plethystic formulas for permutation enumeration
- Local extrema in random permutations and the structure of longest alternating subsequences
- Context-free grammars for several polynomials associated with Eulerian polynomials
- The peak statistics on simsun permutations
- On the alternating runs polynomial in type B and type D Coxeter groups
- Counting permutations by runs
- Counting permutations by simsun successions
- Average length of the longest \(k\)-alternating subsequence
- Online Selection of Alternating Subsequences from a Random Sample
- Sharp large deviations and concentration inequalities for the number of descents in a random permutation
- Longest alternating subsequences of \(k\)-ary words
- An explicit formula for the number of permutations with a given number of alternating runs
- Optimal online selection of an alternating subsequence: a central limit theorem
- Counting permutations by their alternating runs
- Homomorphisms on noncommutative symmetric functions and permutation enumeration
- Some combinatorial arrays related to the Lotka-Volterra system
- Eulerian polynomials and descent statistics
- Longest monotone subsequences and rare regions of pattern-avoiding permutations
- \(q\)-log-convexity from linear transformations and polynomials with only real zeros
- The length of the initial longest increasing sequence in a permutation
- Two-sided permutation statistics via symmetric functions
- A central limit theorem for temporally nonhomogenous Markov chains with applications to dynamic programming
- On weak twins and up-and-down sub-permutations
- Descent-inversion statistics in riffle shuffles
- Longest alternating subsequences in pattern-restricted permutations
- Eulerian pairs and Eulerian recurrence systems
- David-Barton type identities and alternating run polynomials
- The Variance and the Asymptotic Distribution of the Length of Longest $k$-alternating Subsequences
- On the number of reflexive and shared nearest neighbor pairs in one-dimensional uniform data
- Several variants of the Dumont differential system and permutation statistics
- A grammatical calculus for peaks and runs of permutations
- Generating functions of permutations with respect to their alternating runs
- Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three
- Counting signed permutations by their alternating runs
- On weak twins and up-and-down subpermutations
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)
