Square-free word

Under a square-free word (English square free word) is understood in theoretical computer science, a word that contains no ( non-empty ) square of another word.

Definition

A square ( square Sheet ) is the second power of a word, for example. In the natural word formation such words are called reduplicated words. Examples of such are mom, dad and sweet. A square -free word is then a word that contains no non- empty square itself. For example, the word ship, abc is square-free, on the other hand not because it contains the square ff.

A similar definition can be used for other mathematical objects give, see square-free.

Properties

The single binary, that is consisting of only two letters, square-free words are a, b, ab, ba, aba and bab. For an alphabet of at least three letters there are arbitrarily long square-free words.

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, ... 4, 12, 36, 96, 264, 696, ... ( sequence A051041 in OEIS ).