The most unbalanced words 0q−p1p and majorization

Abstract

<p> A finite word w &isin; {0, 1}&lowast; is balanced if for every equal-length factors u and v of every<br /> cyclic shift of w we have ||u|1 &minus; |v|1| &le; 1. This new class of finite words was defined in<br /> [O. Jenkinson and L. Q. Zamboni, Characterisations of balanced words via orderings,<br /> Theoret. Comput. Sci. 310(1&ndash;3) (2004) 247&ndash;271]. In [O. Jenkinson, Balanced words and<br /> majorization, Discrete Math. Algorithms Appl. 1(4) (2009) 463&ndash;484], there was proved<br /> several results considering finite balanced words and majorization. One of the main<br /> results was that the base-2 orbit of the balanced word is the least element in the set of<br /> orbits with respect to partial sum. It was also proved that the product of the elements<br /> in the base-2 orbit of a word is maximized precisely when the word is balanced. It turns<br /> out that the words 0q&minus;p1p have similar extremal properties, opposite to the balanced<br /> words, which makes it meaningful to call these words the most unbalanced words. This<br /> paper contains the counterparts of the results mentioned above. We will prove that the<br /> orbit of the word u = 0q&minus;p1p is the greatest element in the set of orbits with respect<br /> to partial sum and that it has the smallest product. We will also prove that u is the<br /> greatest element in the set of orbits with respect to partial product.</p>