Quadratfreies Wort

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

Definition

Ein Quadrat (engl. square) ist die zweite Potenz eines Wortes, zum Beispiel (abc)² = 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 und bab. 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).

Weblinks

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

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).