A1 Refereed original research article in a scientific journal
The most unbalanced words 0q−p1p and majorization
Authors: Jetro Vesti
Publisher: World Scientific
Publication year: 2015
Journal: Discrete Mathematics, Algorithms and Applications
Journal acronym: DMAA
Article number: 1550028
Volume: 7
Issue: 3
Number of pages: 22
ISSN: 1793-8309
eISSN: 1793-8317
DOI: https://doi.org/10.1142/S1793830915500287
Web address : http://www.worldscientific.com/toc/dmaa/07/03
A finite word w ∈ {0, 1}∗ is balanced if for every equal-length factors u and v of every
cyclic shift of w we have ||u|1 − |v|1| ≤ 1. This new class of finite words was defined in
[O. Jenkinson and L. Q. Zamboni, Characterisations of balanced words via orderings,
Theoret. Comput. Sci. 310(1–3) (2004) 247–271]. In [O. Jenkinson, Balanced words and
majorization, Discrete Math. Algorithms Appl. 1(4) (2009) 463–484], there was proved
several results considering finite balanced words and majorization. One of the main
results was that the base-2 orbit of the balanced word is the least element in the set of
orbits with respect to partial sum. It was also proved that the product of the elements
in the base-2 orbit of a word is maximized precisely when the word is balanced. It turns
out that the words 0q−p1p have similar extremal properties, opposite to the balanced
words, which makes it meaningful to call these words the most unbalanced words. This
paper contains the counterparts of the results mentioned above. We will prove that the
orbit of the word u = 0q−p1p is the greatest element in the set of orbits with respect
to partial sum and that it has the smallest product. We will also prove that u is the
greatest element in the set of orbits with respect to partial product.
Downloadable publication This is an electronic reprint of the original article. |