Quelltext der Seite Quadratfreies Wort

Unter einem '''quadratfreien Wort''' (englisch {{lang|en|''squarefree word''}}) versteht man in der [[Theoretische Informatik|Theoretischen Informatik]] ein [[Wort (Theoretische Informatik)|Wort]], das kein (nicht-[[Leeres Wort|leeres]]) Quadrat eines anderen Wortes enthält.

== Definition ==
Ein Quadrat ({{enS|square}}) ist die zweite [[Wort (Theoretische Informatik)#Potenz|Potenz eines Wortes]], zum Beispiel <math>(abc)^2 = abcabc</math>. In der [[natürliche Sprache|natürlichen]] [[Wortbildung]] werden solche Wörter als [[Reduplikation (Sprache)|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.&nbsp;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, … ({{OEIS|A006156}}).<br />
Die Anzahl der quaternären quadratfreien Wörter der Länge n = 1, 2, … ist 4, 12, 36, 96, 264, 696, … ({{OEIS|A051041}}).

== Literatur ==
* {{Literatur
   |Autor=Jean-Paul Allouche, Jeffrey Shallit
   |Titel=Automatic sequences: theory, applications, generalizations
   |Verlag=Cambridge University Press
   |Datum=2003
   |ISBN=0-521-82332-3
   |Online={{Google Buch|BuchID=2ZsSUStt96sC|Seite=14}}}}

== Weblinks ==
* {{MathWorld |id=SquarefreeWord |title=Squarefree Word}}

[[Kategorie:Theorie formaler Sprachen]]