https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Quadratfreies_Wort Quadratfreies Wort - Versionsgeschichte 2026-06-20T19:56:55Z Versionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale Kopie MediaWiki 1.43.8 https://wiki-de.moshellshocker.dns64.de/index.php?title=Quadratfreies_Wort&diff=2025508&oldid=prev imported>D3rT!m: /* Eigenschaften */ leeres Wort ergänzt 2022-08-11T21:54:38Z <p><span class="autocomment">Eigenschaften: </span> leeres Wort ergänzt</p> <p><b>Neue Seite</b></p><div>Unter einem &#039;&#039;&#039;quadratfreien Wort&#039;&#039;&#039; (englisch {{lang|en|&#039;&#039;squarefree word&#039;&#039;}}) 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.<br /> <br /> == Definition ==<br /> Ein Quadrat ({{enS|square}}) ist die zweite [[Wort (Theoretische Informatik)#Potenz|Potenz eines Wortes]], zum Beispiel &lt;math&gt;(abc)^2 = abcabc&lt;/math&gt;. In der [[natürliche Sprache|natürlichen]] [[Wortbildung]] werden solche Wörter als [[Reduplikation (Sprache)|reduplizierte Wörter]] bezeichnet. Beispiele für solche sind &#039;&#039;Mama&#039;&#039;, &#039;&#039;Papa&#039;&#039; und &#039;&#039;Bonbon&#039;&#039;. Ein quadratfreies Wort ist dann ein Wort, das selbst kein nicht-leeres Quadrat enthält. Zum Beispiel ist das Wort &#039;&#039;abc&#039;&#039; quadratfrei, &#039;&#039;Schiff&#039;&#039; dagegen nicht, weil es das Quadrat &#039;&#039;ff&#039;&#039; enthält.<br /> <br /> Eine vergleichbare Definition lässt sich auch für andere mathematische Objekte geben, siehe [[quadratfrei]].<br /> <br /> == Eigenschaften ==<br /> Die einzigen binären, d.&amp;nbsp;h. aus nur zwei Buchstaben bestehenden, quadratfreien Wörter sind &#039;&#039;a&#039;&#039;, &#039;&#039;b&#039;&#039;, &#039;&#039;ab&#039;&#039;, &#039;&#039;ba&#039;&#039;, &#039;&#039;aba&#039;&#039;, &#039;&#039;bab&#039;&#039; und das leere Wort. Für ein Alphabet aus mindestens drei Buchstaben gibt es jedoch beliebig lange quadratfreie Wörter.<br /> <br /> 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}}).&lt;br /&gt;<br /> Die Anzahl der quaternären quadratfreien Wörter der Länge n = 1, 2, … ist 4, 12, 36, 96, 264, 696, … ({{OEIS|A051041}}).<br /> <br /> == Literatur ==<br /> * {{Literatur<br /> |Autor=Jean-Paul Allouche, Jeffrey Shallit<br /> |Titel=Automatic sequences: theory, applications, generalizations<br /> |Verlag=Cambridge University Press<br /> |Datum=2003<br /> |ISBN=0-521-82332-3<br /> |Online={{Google Buch|BuchID=2ZsSUStt96sC|Seite=14}}}}<br /> <br /> == Weblinks ==<br /> * {{MathWorld |id=SquarefreeWord |title=Squarefree Word}}<br /> <br /> [[Kategorie:Theorie formaler Sprachen]]</div> imported>D3rT!m