¿Cuál es una fórmula para el número de cadenas sin repeticiones?

8

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.sAts1<|t|<|s|tsA={a,b}aaa aaabab

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:{a,b}

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.A×A××A(k-4 times)×R×RRk4

Dan Donnelly
fuente
1
¿Por qué no hay una copia disjunta en ? ¿No es una subcadena válida de , es decir, ? ¿Puedes dar un par de ejemplos más para aclarar lo que debe y no debe contarse? aaat=as=aas=tt
Ran G.
1
Avisorequisito. Avíseme si / cómo puedo escribir mi publicación más claramente. 1<|t|
Dan Donnelly
Sí, perdí este requisito. Tiene más sentido ahora.
Ran G.
1
No veo cómo (con un alfabeto de 2 letras, por ejemplo) puede construir una cadena de longitud (digamos) 10 sin repeticiones. es decir, el número deseado debe estar limitado por una función de k independiente de n
Suresh
2
Solo puedo decir que para el alfabeto de tamaño cadena más larga posible sin repeticiones, es es porque puede tener cadenas de longitud con los mismos elementos, y se debe a que solo tiene combinación diferente de estos elementos, y agregar nuevas combinaciones hace que se repita. (Considero que dices sobre la repetición disjunta). n
2(norte2)+3norte
3norte32(norte2)2(norte2)

Respuestas:

1

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Σ XyXXΣ2yΣ

Reclamación: Para un alfabeto finito dado con , no hay palabras sin repetición de longitud mayor que .ΣEl |ΣEl |=k2k2+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. w2k2+2w=una0 0una0 0...unak2unak2wunayounayounajunajyojk2+1El |Σ2El |=k2w

Tenga en cuenta que esta es una prueba aproximada: los factores pueden crear una repetición incluso antes.unayounayo+1


Notación:

  • Σk=yo=kΣyo=Σyo=0 0k-1Σyo
  • "factor" = "subword" = "subcadena"
Rafael
fuente
Esto realmente no responde la pregunta. Solo ha demostrado un límite superior muy crudo y bastante obvio, la pregunta solicitó una fórmula exacta.
Gilles 'SO- deja de ser malvado'
@Gilles: Al principio leí mal la pregunta, pero pensé que podría dejar lo que escribí aquí para otros (por ejemplo, Kaveh, quien afirmó que había infinitas palabras de este tipo).
Raphael
Mi comentario es más estricto que tu respuesta.