Quiero contar el número de cadenas sobre un alfabeto finito , que no contiene repeticiones, y con eso me refiero a cualquier subcadena de ,, no hay una copia disjunta de en . Por ejemplo, deje . Entonces es una de las cadenas que quiero contar, ya que para la subcadena , no hay copias disjuntas. Sin embargo, contiene tal repetición.
Si alguien ya ha descubierto una fórmula útil, por favor enlace. De lo contrario, me referiré a esta publicación en cualquier artículo que escriba, si uso la respuesta de alguien.
Aquí hay otro ejemplo. Intentemos construir una cadena larga sobre , que no contenga repeticiones:
aaa (no puede ser a)
aaab (a o b)
aaabbb (no puede ser b)
aaabbba (no puede ser b o a)
aaaba (no puede ser a o b)
Si construimos un árbol, podríamos contar el número de nodos, pero quiero una fórmula.
Editar: Bueno, no es tan desalentador como pensé por primera vez si convertimos esto en un problema de elección de contenedores. Un conjunto de cadenas de longitud k con al menos una repetición es igual al conjunto que es la unión de todas las permutaciones del producto cartesiano: donde es la repetición requerida. No sé si eso es útil, pero sonó profesional :) De todos modos, que sean | A | bins, elija cualquiera de los dos (incluso si es el mismo) para ser la repetición, luego elija más y multiplique (los primeros 4 ya están elegidos, ¿ve?). Ahora solo necesito encontrar esa fórmula a partir de matemáticas discretas.
fuente
Respuestas:
Esto responde a la pregunta después del número de palabras libres de repetición por tamaño, lo que implica que incluso existe la cantidad deseada.
Definición: Llame repetición si y solo si no contiene un factor con e .w ∈ Σ x yX x ∈Σ≥ 2 y∈Σ∗
Reclamación: Para un alfabeto finito dado con , no hay palabras sin repetición de longitud mayor que .Σ El | Σ | =k 2k2+ 1
Idea de prueba: según el principio del agujero de paloma. Tome una palabra de longitud (o una palabra más larga y considere su prefijo de esta longitud), es decir . Suponga que tiene repetición; eso significa que para todo (de lo contrario, tuvimos una repetición). Por lo tanto, hay muchos pares de símbolos; esto contradice . Entonces no está libre de repeticiones.w 2k2+ 2 w =una0 0una′0 0...unak2una′k2 w unayouna′yo≠unajuna′j i ≠ j k2+ 1 El |Σ2El | =k2 w □
Tenga en cuenta que esta es una prueba aproximada: los factores pueden crear una repetición incluso antes.una′younai + 1
Notación:
fuente