Combinatorics · Lesson 4

Counting Unbordered Words

Practice this topic →

The counting problem

Let $U_k\left(n\right)$ be the set of unbordered words of length $n$ over a $k$-letter alphabet, and write $u_k\left(n\right)=\left|U_k\right(n\left)\right|$.

Every word is either bordered or unbordered, but not both, so:

The Nielsen recurrence

The key fact: if $w=uv$ is split into two halves, then inserting a symbol into the middle preserves “unbordered” status in exactly the ways captured below.

Intuition for the odd case: an unbordered word of length $n-1$ stays unbordered when a symbol is inserted in the middle, and every length-$n$ unbordered word arises exactly this way.

The even case subtracts exactly the words that would gain a border by that middle insertion: those of the form $zz$ where $z$ is an unbordered word of length $n/2$.

Exploring the recurrence

Use the table below to see how $u_k\left(n\right)$ and $b_k\left(n\right)$ grow:

For example, $u_2\left(4\right)$: the binary unbordered words of length 4 are 0001, 0011, 0111, 1000, 1100, 1110 — six of them.

A limiting frequency

It can be shown that $u_k\left(n\right)/k^n$ converges as $n\to \infty$. For binary words the limit is about $0.267786$ — roughly a quarter of all binary words are unbordered.

Practice

Compute the count

Practice this topic →Every quiz from this lesson, at four difficulties.