Balanced word: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
Let ''d'' ≥ 0. A [[word]] or [[necklace]] ''s'' | Let ''d'' ≥ 0. A [[word]] or [[necklace]] ''s'' is ''d''-'''balanced''' if its '''balance''' satisfies the following: | ||
<math> \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 d,</math> | <math> \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 d,</math> | ||
Revision as of 00:33, 24 December 2023
Let d ≥ 0. A word or necklace s is d-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 d, }[/math]
where |u|xi is the number of occurrences of the letter xi in the word u. A scale is balanced if it is 1-balanced.
A balanced word or necklace in N letters has a maximum variety bound of [math]\displaystyle{ N \choose {\lceil N/2 \rceil} }[/math].