Asymptotic Bounds for the Number of Closed and Privileged Words

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 closed if w is of length at most 1 or if w has a border that occurs exactly twice in w. A word w is said to be privileged if w is of length at most 1 or if w has a privileged border that occurs exactly twice in w. Let Cₖ (n) (resp. Pₖ (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ₖ (n) and Pₖ (n). We completely resolve the asymptotic behaviour of Cₖ (n). We also nearly completely resolve the asymptotic behaviour of Pₖ (n) by giving a family of upper and lower bounds that are separated by a factor that grows arbitrarily slowly.