Square free word

Under a square-free word (engl. Square free word ) is understood in the theoretical computer science , a word which is not a (non- empty ) contains square of another word.

definition

A square ( English square ) is the second power of a word , for example . In natural word formation , such words are called reduplicated words . Examples of such are mom , dad, and candy . A square-free word is then a word that itself does not contain a non-empty square. For example, the word abc is square-free, but Schiff is not, because it contains the square ff . ${\displaystyle (abc)^{2}=abcabc}$

A comparable definition can also be given for other mathematical objects, see free of squares .

properties

The only binary, i.e. H. Square-free words consisting of only two letters are a , b , ab , ba , aba and bab . For an alphabet of at least three letters, however, there are no square words of any length.

The number of ternary square-free words of length n = 1, 2,… is 1, 3, 6, 12, 18, 30, 42, 60,… (sequence A006156 in OEIS ).
The number of quaternary square-free words of length n = 1, 2,… is 4, 12, 36, 96, 264, 696,… (sequence A051041 in OEIS ).

literature

• Jean-Paul Allouche, Jeffrey Shallit: Automatic sequences: theory, applications, generalizations . Cambridge University Press, 2003, ISBN 0-521-82332-3 ( limited preview in Google Book Search).

Web links

• Eric W. Weisstein : Squarefree Word . In: MathWorld (English).