CLR cover

Problem 144: Counting unbordered words and relatives

\( \)

We assume, for simplicity, that the alphabet is binary. A word is called unbordered if it has no proper border. Denote by $\un(n)$ the number of unbordered binary words of length $n$. We have: \[\un(0),\un(1),\un(3),\un(4),\ldots = \, 1, 2, 2, 4, 6, 12, 20, 40, 74,\ldots.\]

A word $w$ is unbordered if and only if it has no border of length at most $|w|/2$.

There are $2^{n-k}$ binary words with border of size $k$, for $k\le n/2$. Due to the observation we have an exponential lower bound on $\un(n)$ \[\un(n)\geq 2^n-2^{n-1}-2^{n-2}-\cdots - 2^{\lceil n/2\rceil}\, \geq 2^{n/2}.\]

Denote by $\vv(n)$ and $\tv(n)$ the number of binary words of length $n$ without nontrivial prefix palindrome of even length and odd length, respectively.

Describe algorithms computing $\un(n),\, \vv(n)$ and $\tv(n)$ in $O(n)$ time.

References