Quadratfreies Wort
Unter einem quadratfreien Wort (englisch Vorlage:Lang) versteht man in der Theoretischen Informatik ein Wort, das kein (nicht-leeres) Quadrat eines anderen Wortes enthält.
Definition
Ein Quadrat (Vorlage:EnS) ist die zweite Potenz eines Wortes, zum Beispiel . 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, … (Vorlage:OEIS).
Die Anzahl der quaternären quadratfreien Wörter der Länge n = 1, 2, … ist 4, 12, 36, 96, 264, 696, … (Vorlage:OEIS).