Enumerating binary words restricted by subsequence frequency

Abstract

Let $p$ be a binary word of length $\ell$ with $r\ge 2$ runs. Previously known only for $k\le 4$, we show for $n$ sufficiently large that the number of binary words of length $n$ with exactly $k$ subsequences equal to $p$ is polynomial in $n$ of degree at most $\ell -r+1$ for any positive integer $k$. We also prove a sharp upper bound on the number of subsequences equal to $p$ of a binary word $w$ in terms of the runs of $p$ and $w$.

21 pages