Combinatorics · Lesson 5

Generating Unbordered Words

Practice this topic →

The GenU algorithm

The Nielsen recurrence tells us how many unbordered words there are, but not which ones. The GenU algorithm lists every unbordered word of length n, exactly once.

The idea is to build words from both ends inward:

  1. Start with every two-letter word ab with a≠b (all such words are unbordered).
  2. Insert two middle symbols at a time, extending both ends.
  3. Never allow an insertion that would make the two halves equal — that is exactly what would create a border.
Length n:

There are 6 unbordered binary words of length 4.

Generated by the GenU algorithm, growing each word from both ends: start with a two-letter word whose letters differ, then insert two middle symbols — never allowing the two halves to become equal.

Why this works

The only way the even-length extension uabv becomes bordered is if the newly formed middle ua=bv is itself a full word — which the algorithm checks before inserting.

Efficiency

Every recursive call in GenU produces at least one output word (or a subtree that does), so the total work is proportional to the number uk(n) of generated words. Excluding the cost of printing each word, GenU runs in constant-amortized time.

Practice

Which words are unbordered?

Which of these words are unbordered? Select all that apply.

Which of these words are unbordered? Select all that apply.

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

References