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

DOI10.46298/DMTCS.10296MaRDI QIDQ6131790zbMATH OpenOpenAlexFDO

Authors Yunus Emre Demirci, Ümit Işlak

Publication date 18 April 2024

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.12459

zbMATH Keywords

central limit theorempeak\(k\)-alternating subsequencesalternating subsequences

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Central limit and other weak theorems (60F05) Exact enumeration problems, generating functions (05A15)

Abstract: We obtain an explicit formula for the variance of the number of $k$-peaks in a uniformly random permutation. This is then used to obtain an asymptotic formula for the variance of the length of longest $k$-alternating subsequence in random permutations. Also a central limit is proved for the latter statistic.

Recommendations

• On the limiting distribution for the length of the longest alternating sequence in a random permutation
• A probabilistic approach to the asymptotics of the length of the longest alternating subsequence
• Local extrema in random permutations and the structure of longest alternating subsequences
• On increasing subsequences of random permutations
• Longest alternating subsequences of permutations

This page was built for publication: The Variance and the Asymptotic Distribution of the Length of Longest $k$-alternating Subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131790)