Longest alternating subsequences of permutations
From MaRDI portal
(Redirected from Publication:841561)
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)- 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
- Online Selection of Alternating Subsequences from a Random Sample
- On weak twins and up-and-down subpermutations
- Longest monotone subsequences and rare regions of pattern-avoiding permutations
- 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
- Enumeration of permutations by number of alternating runs
- Several variants of the Dumont differential system and permutation statistics
- Martingales and descent statistics
- An explicit formula for the number of permutations with a given number of alternating runs
- Average length of the longest \(k\)-alternating subsequence
- Counting permutations by simsun successions
- Eulerian polynomials and descent statistics
- Large deviations for the longest alternating and the longest increasing subsequence in a random permutation avoiding a pattern of length three
- Plethystic formulas for permutation enumeration
- Counting permutations by their alternating runs
- Generating functions of permutations with respect to their alternating runs
- On weak twins and up-and-down sub-permutations
- On the longest \(k\)-alternating subsequence
- Sharp large deviations and concentration inequalities for the number of descents in a random permutation
- Optimal online selection of an alternating subsequence: a central limit theorem
- A central limit theorem for temporally nonhomogenous Markov chains with applications to dynamic programming
- Local extrema in random permutations and the structure of longest alternating subsequences
- Two-sided permutation statistics via symmetric functions
- Counting signed permutations by their alternating runs
- Eulerian pairs and Eulerian recurrence systems
- Homomorphisms on noncommutative symmetric functions and permutation enumeration
- A grammatical calculus for peaks and runs of permutations
- Longest alternating subsequences in pattern-restricted permutations
- Longest alternating subsequences of \(k\)-ary words
- A note on a permutation statistic
- David-Barton type identities and alternating run polynomials
- Descent-inversion statistics in riffle shuffles
- The length of the initial longest increasing sequence in a permutation
- On the alternating runs polynomial in type B and type D Coxeter groups
- 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)
