Quadratfreies Wort

Unter einem quadratfreien Wort (englisch squarefree word) versteht man in der Theoretischen Informatik ein Wort, das kein (nicht-leeres) Quadrat eines anderen Wortes enthält.

Definition

Ein Quadrat (englisch square) ist die zweite Potenz eines Wortes, zum Beispiel $(abc)^{2}=abcabc$. In der natürlichen Wortbildung werden solche Wörter als reduplizierte Wörter bezeichnet. Beispiele für solche sind Mama, Papa und Bonbon. Ein quadratfreies Wort ist dann ein Wort, das selbst kein nicht-leeres Quadrat enthält. Zum Beispiel ist das Wort abc quadratfrei, Schiff dagegen nicht, weil es das Quadrat ff enthält.

Eine vergleichbare Definition lässt sich auch für andere mathematische Objekte geben, siehe quadratfrei.

Eigenschaften

Die einzigen binären, d. h. aus nur zwei Buchstaben bestehenden, quadratfreien Wörter sind a, b, ab, ba, aba, bab und das leere Wort. Für ein Alphabet aus mindestens drei Buchstaben gibt es jedoch beliebig lange quadratfreie Wörter.

Die Anzahl der ternären quadratfreien Wörter der Länge n = 1, 2, … ist 1, 3, 6, 12, 18, 30, 42, 60, … (Folge A006156 in OEIS).
Die Anzahl der quaternären quadratfreien Wörter der Länge n = 1, 2, … ist 4, 12, 36, 96, 264, 696, … (Folge A051041 in OEIS).

Literatur

• Jean-Paul Allouche, Jeffrey Shallit: Automatic sequences: theory, applications, generalizations. Cambridge University Press, 2003, ISBN 0-521-82332-3 (eingeschränkte Vorschau in der Google-Buchsuche). 

Weblinks

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