Balanced word: Difference between revisions
Tags: Mobile edit Mobile web edit |
No edit summary Tags: Mobile edit Mobile web edit |
||
| Line 1: | Line 1: | ||
A [[word]] or [[necklace]] ''s'' is '''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 1,</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 1,</math> | ||
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 on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>. | * A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>. | ||