Balanced word

Let d ≥ 0. A word or necklace s is balanced if its balance satisfies the following:

[math]\displaystyle{ \operatorname{balance}(s) := \max \big\{ \big| |w|_{x_i} - |w'|_{x_i} \big| : x_i \text{ is a letter of }s\text{ and }k = \operatorname{len}(w) = \operatorname{len}(w') \big\} \leq 1, }[/math]

where |u|_xi is the number of occurrences of the letter x_i in the word u.

Properties

• A balanced word or necklace in N letters has a maximum variety bound of [math]\displaystyle{ N \choose {\lceil N/2 \rceil} }[/math].
• If w is an aperiodic infinite balanced word, then w is constructed via a finite sequence of congruence substitutions from infinite balanced words on 2 letters. A congruence substitution involves replacing the kth occurrence of a fixed letter j in w with the kth letter of u where u is a "congruence word" over a set of letters disjoint from that of w for all positive integers k.