Fraenkel word

In combinatorics on words, the Fraenkel word over n letters [math]\displaystyle{ \mathbf{0}, \mathbf{1}, ..., (\mathbf{n-1}) }[/math] is defined recursively by

[math]\displaystyle{ \displaystyle{ \begin{align*} F_1 &= \mathbf{0}, \\ F_2 &= \mathbf{010}, \\ F_3 &= \mathbf{0102010}, \\ &\ \ \vdots \\ F_{n} &= F_{n-1}(\mathbf{n-1})F_{n-1}. \end{align*}} }[/math]

Fraenkel words are named after mathematician Aviezri S. Fraenkel.

Facts

Below we denote the length of a word w by |w| and the number of occurrences of the letter i in w as |w|_i, as is standard notation in combinatorics on words. The notation w(u₀, ..., u_r−1) represents the word w in 0, 1, ..., r−1 but with i replaced by the word u_i.

Fraenkel words are balanced

Theorem — For all n ≥ 1, the n-ary Fraenkel word is balanced as a circular word.

Open problems

For circular words (equivalently, infinite periodic words), Fraenkel's conjecture asserts that the only balanced circular words over n ≥ 3 letters with letter occurrences pairwise distinct are (letter reassignments of) [math]\displaystyle{ F_n. }[/math] The conjecture is known to be true for 3 ≤ n ≤ 7.