Upper bound for the number of closed and privileged words

Abstract

A non-empty word $w$ is a border of the word $u$ if $|w|<|u|$ and $w$ is both a prefix and a suffix of $u$. A word $u$ with the border $w$ is closed if $u$ has exactly two occurrences of $w$. A word $u$ is privileged if $|u|\le 1$ or if $u$ contains a privileged border $w$ that appears exactly twice in $u$. Peltomäki (2016) presented the following open problem: "Give a nontrivial upper bound for $B(n)$", where $B(n)$ denotes the number of privileged words of length $n$. Let $D(n)$ denote the number of closed words of length $n$. Let $q>1$ be the size of the alphabet. We show that there is a positive real constant $c$ such that \[D(n)\leq c\ln{n}\frac{q^{n}}{\sqrt{n}}\mbox{, where }n>1\mbox{.}\] Privileged words are a subset of closed words, hence we show also an upper bound for the number of privileged words.