Average length of the longest k-alternating subsequence

2015/02/05 by Tommy Wuxing Cai, Cai, Tommy Wuxing
Computer Science · Mathematics · #05A05 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1502.01543

openalex publication_date 2015/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove a conjecture of Drew Armstrong on the average maximal length of k-alternating subsequence of permutations. The k=1 case is a well-known result of Richard Stanley.

Related

• Longest alternating subsequences of permutations
• On the longest k-alternating subsequence
• On the Limiting Distribution for the Longest Alternating Sequence in a Random Permutation
• Longest Common Subsequences in Sets of Permutations
• A Note on the Expected Length of the Longest Common Subsequences of two i.i.d. Random Permutations