The variance and the asymptotic distribution of the length of longest k-alternating subsequences
Discrete Mathematics and Theoretical Computer Science, cilt.25, sa.1, 2023 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 25 Sayı: 1
- Basım Tarihi: 2023
- Doi Numarası: 10.46298/dmtcs.10296
- Dergi Adı: Discrete Mathematics and Theoretical Computer Science
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, MathSciNet, zbMATH, Directory of Open Access Journals
- Anahtar Kelimeler: Alternating subsequences, central limit theorem, k-alternating subsequences, Peak
- Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
- Boğaziçi Üniversitesi Adresli: Evet
Özet
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.