The asymptotic number of prefix normal words

Abstract

We show that the number of prefix normal binary words of length $n$ is $2^{n-\Theta ((\log n{)}^2)}$. We also show that the maximum number of binary words of length $n$ with a given fixed prefix normal form is $2^{n-O(\sqrt{n\log n})}$.

9 pages

References in corpus (1)

• On Prefix Normal Words and Prefix Normal Forms