Upper bound for the number of closed and privileged words
share
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|≤ 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)≤ clnnq^n/√(n)n>1 Privileged words are a subset of closed words, hence we show also an upper bound for the number of privileged words.
READ FULL TEXT