A word w is primitive if w cannot be written in the form uk for any k greater than 1, and w is bordered if some proper prefix of w is also a proper suffix. The authors consider words in which the number of occurrences of each letter (the word’s weight) is fixed, and present new formulas for counting the number of primitive and bordered words under this constraint. Their derivation of the formula for the number of primitive words of fixed weight is a straightforward extension of the previously known expression for counting primitive words of fixed length. The formula for the number of unbordered words of a given weight is slightly harder to obtain, and is derived by first considering two-letter alphabets and then generalizing to alphabets of arbitrary size. The paper concludes with an equation giving the number of wor!ds of fixed length (with no restrictions on weight) that have exactly one border.
Such a brief paper would normally be classified as a short communication or even a note, rather than a full paper. However, it appears in a special issue entitled “The Art of Theory” in honor of Antonio Restivo, and, in this context, it serves as a short and elegant illustration of the power of formal techniques. Moreover, a substantial portion of the paper reviews the derivations of earlier results--for example, it includes the classical Möbius inversion derivation for the number of primitive words of a fixed length. As a result, the paper is self-contained and accessible to a wide audience.
