# Average length of the longest k-alternating subsequence

@article{Cai2015AverageLO, title={Average length of the longest k-alternating subsequence}, author={W. Cai}, journal={J. Comb. Theory, Ser. A}, year={2015}, volume={134}, pages={51-57} }

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.

#### Topics from this paper

#### One Citation

The Variance and the Asymptotic Distribution of the Length of Longest $k$-alternating Subsequences

- Mathematics
- 2021

We obtain an explicit formula for the variance of the length of longest k-alternating subsequence in a uniformly random permutation. Also a central limit is proved for the same statistic.

#### References

SHOWING 1-4 OF 4 REFERENCES

On the Longest $k$-Alternating Subsequence

- Mathematics, Computer Science
- Electron. J. Comb.
- 2015

We show that the longest $k$-alternating substring of a random permutation has length asymptotic to $2(n-k)/3$.

Longest alternating subsequences of permutations

- Mathematics
- 2005

The length is(w) of the longest increasing subsequence of a permutation w in the symmetric group Sn has been the object of much investigation. We develop comparable results for the length as(w) of… Expand

Increasing and decreasing subsequences and their variants

- Mathematics
- 2006

We survey the theory of increasing and decreasing subsequences of permutations.
Enumeration problems in this area are closely related to the RSK algorithm. The asymptotic
behavior of the expected… Expand

Enumerative Combinatorics Problem Session, in Oberwolfach

- Report No. 12/2014,
- 2014