Palabra sin cuadrados

En combinatoria , una palabra sin cuadrados es una palabra (una secuencia de símbolos) que no contiene cuadrados. Un cuadrado es una palabra de la forma XX , donde X no está vacío. Por lo tanto, una palabra sin cuadrados también se puede definir como una palabra que evita el patrón XX .

En un alfabeto binario , las únicas palabras libres de cuadrados son la palabra vacía , y .${\ estilo de visualización \ {0,1\}}$${\ estilo de visualización \ epsilon, 0,1,01,10,010}$${\ estilo de visualización 101}$

Sobre un alfabeto ternario , hay infinitas palabras sin cuadrados. Es posible contar el número de palabras libres de cuadrados ternarios de longitud n .${\ estilo de visualización \ {0,1,2\}}$${\ estilo de visualización c (n)}$

Este número está acotado por , donde . ^[2] El límite superior de se puede encontrar a través del lema de Fekete y la aproximación por autómatas . El límite inferior se puede encontrar encontrando una sustitución que conserve la libertad de cuadrados. ^[2]${\displaystyle c(n)=\Theta (\alpha ^{n})}$${\textstyle 1.3017597<\alfa <1.3017619}$${\ estilo de visualización \ alfa}$

Dado que hay infinitas palabras sin cuadrados en alfabetos de tres letras, esto implica que también hay infinitas palabras sin cuadrados en un alfabeto con más de tres letras.

Extender una palabra sin cuadrados para evitar ab .