Fraenkel word: Difference between revisions
mNo edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
\end{align*}} | \end{align*}} | ||
</math> | </math> | ||
Fraenkel words are named after mathematician Aviezri S. Fraenkel. | |||
== Facts == | == Facts == | ||
{{theorem|contents=As circular words, Fraenkel words are [[balanced]].}} | {{theorem|contents=As circular words, Fraenkel words are [[balanced]].}} | ||
Revision as of 22:20, 9 February 2024
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
Theorem — As circular words, Fraenkel words are balanced.
TODO: proof
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][1] The conjecture is known to be true for 3 ≤ n ≤ 7.
References
- ↑ Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.