Asymptotic bounds for the number of closed and privileged words

Daniel Gabric

Published 2022-06-28Version 1

A word $w$ has a border $u$ if $u$ is a non-empty proper prefix and suffix of $u$. A word $w$ is said to be \emph{closed} if $|w| \leq 1$ or if $w$ has a border that occurs exactly twice in $w$. A word $w$ is said to be \emph{privileged} if $|w| \leq 1$ or if $w$ has a privileged border that occurs exactly twice in $w$. Let $C_k(n)$ (resp. $P_k(n)$) be the number of length-$n$ closed (resp. privileged) words over a $k$-letter alphabet. In this paper we improve existing upper and lower bounds on $C_k(n)$ and $P_k(n)$. We prove that $C_k(n) \in \Theta(\frac{k^n}{n})$. Let $\log_k^{\circ 0}(n) = n$ and $\log_k^{\circ j}(n) = \log_k(\log_k^{\circ j-1}(n))$ for $j\geq 1$. We also prove that for all $j\geq 0$ there exist constants $N_j$, $c_j$, and $c_j'$ such that \[c_j\frac{k^n}{n\log_k^{\circ j}(n)\prod_{i=1}^j\log_k^{\circ i}(n)}\leq P_k(n) \leq c_j'\frac{k^n}{n\prod_{i=1}^j\log_k^{\circ i}(n)}\] for all $n>N_j$.