Balanced word: Difference between revisions
No edit summary |
Tags: Mobile edit Mobile web edit |
||
| Line 5: | Line 5: | ||
where |''u''|<sub>''x''<sub>''i''</sub></sub> is the number of occurrences of the letter ''x''<sub>''i''</sub> in the word ''u''. | where |''u''|<sub>''x''<sub>''i''</sub></sub> is the number of occurrences of the letter ''x''<sub>''i''</sub> in the word ''u''. | ||
== Properties == | == Properties == | ||
A balanced word or necklace in ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>. | * A balanced word or necklace in ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>. | ||
* In the general rank-''d'' case, if ''w'' is an aperiodic infinite billiard 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 ''k''th letter of ''w'' with the ''k''th letter of ''a'' where ''a'' has a set of letters disjoint from that of ''w'' for all positive integers ''k''.<ref>Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.</ref> | |||
== Generalizations == | == Generalizations == | ||
[[Category:Scale]][[Category:Terms]] | [[Category:Scale]][[Category:Terms]] | ||
[[Category:Combinatorics on words]] | [[Category:Combinatorics on words]] | ||