Most frequent subsequences in a word

Abstract

We prove that every $n$-letter word over $k$-letter alphabet contains some word as a subsequence in at least $k^{n/4k(1+o(1))}$ many ways, and that this is sharp as $k\to \infty$. For fixed $k$, we show that the analogous number deviates from $\hat{I}{¼}_k^n$, for some constant $\hat{I}{¼}_k$, by a factor of at most $n$.

16 pages