Número de palabras con un número mínimo de repeticiones

Question

Dado :

• una longitud de palabra de $n$,
• un conjunto de caracteres $C = \{c_1, ..., c_p\}$,
• y un número mínimo de repeticiones $m$,

Cuántas palabras de $n$ personajes de $C$ que contiene al menos una secuencia de $m$ veces el mismo personaje ?

Tengo un conocimiento muy limitado de la combinatoria y el álgebra, así que por favor, no se lo dan "pistas". Gracias.

Nota : Esta pregunta se pidió por primera vez en stackoverflow.com pero, obviamente, las pruebas de todos los posibles cadena (incluso con accesos directos) es un muy ineficiente forma de solucionar esto, que es la razón por la que vine aquí para una solución matemática (y también porque la matemática es hermoso).

Answer 1

Actualizado: simplificar enormemente.

Deje $P$ ser el alphabeth (conjunto de caracteres) de tamaño. Deje $S(N,M)$ el número de cadenas de longitud $N$ (más que alphabeth) que NO incluye ningún subsequence de $M$ consecutivos caracteres repetidos.

Entonces $$ S(N,M)=\left\{ \begin{array}{ll} P^{N} & N<M \\ (P-1) \sum_{i=1}^{M-1} S(N-i,M) & N \ge M \end{array} \right. $$

Con esto, podemos calcular de forma recursiva los valores de $S(N,M)$ cualquier $N,M,P$.

Por ejemplo.

Esto puede estar relacionado, al menos para $P=2$, a la de Fibonacci M-números de paso (aunque aquí tenemos un los diferentes valores de partida; en cualquier caso, esto sugiere que un explícito de forma cerrada, valor que sería bastante complicado).

Un asintótica puede ser obtenida por un argumento probabilístico (breve explicación añadido) :

Suponga que todas las realizaciones de la secuencia de $N$ personajes son equiprobables, y permite calcular la fracción que siguen a nuestro restricción (todas las carreras tienen la longitud de menos de $M$) como una probabilidad. Vamos $x_i \ge 1$ ($i=1\cdots c$) ser la $i-$th runlength. Tenemos que la suma es fijo ($\sum x_i = N$) y $c$ (número de carreras) es una variable aleatoria. Me dicen que este modelo es asintóticamente equivalente a otro en el que el número de pistas $c$ es fijo y el $x_i$ son iid; y, por tanto, la suma es variable (sino $E[\sum x_i] = c \, E[x_i]= N$). Esto es conceptualmente el mismo como el "Poissonization" método. En nuestro caso, $x_i$ son geométricas variables, con $p = (P-1)/P = 1 - \theta$ (probabilidad de que la ejecución se detiene en el próximo intento).

Debido a que la media de este geométrica variable (con apoyo en $1 \cdots \infty$) $1/p$ obtenemos $c = N (1 -\theta)$ . En el caso de que $x_i < M$ para algunos en particular $i$ puede ser calculada como una suma geométrica como $ 1 -\theta^{M-1}$ y debido a $x_i$ son iid, $P(x_1 < M ;x_2 <M \cdots) =P(x_1<M)^c$ tenemos finalmente obtener la fracción deseada y

$$ S(N,M) \approx P^N \, \left(1-\theta^{M-1}\right)^{N(1-\theta)}, \hspace{1cm} \theta=\frac{1}{P} $$

Answer 2

También hay una buena generación de función para este problema. Fix $p$ y deje $S(n,m)$ el número de palabras de longitud $n$ utilizando en la mayoría de las $p$ distintas letras, con la no repetición de $m$ cartas idénticas en una fila, como se define por leonbloy. A continuación, $$ \sum_{n = 0}^\infty S(n,m) x^n = \frac{1 - x^m}{1 - px - (1-p)x^m}.$$

Si usted no está familiarizado con las funciones de generación, esto significa que usted puede conseguir el número que usted está buscando de forma bastante sencilla de extraer el coeficiente de $x^n$ en la serie de Taylor para la expresión anterior el uso de software matemático como la Salvia, el Mathematica etc. Ya que es racional, es decir, una fracción de polinomios, esto también permite a encontrar otra fórmula recursiva.

Añadido más detalles:

En general racional de generación de función

$$\sum_{n=0}^\infty f(n) x^n = \frac{p(x)}{1 + a_1x + \ldots + a_mx^m}$$

voluntad, para la gran n, obedece a una relación de recurrencia

$$f(n) + a_1f(n-1) + \ldots + a_nf(n-m) = 0.$$

Increíble, ¿no? Véase Richard Stanley - La Combinatoria Enumerativa Vol. 1 Ch. 4, o simplemente en Google. En este caso tenemos el denominador

$$1 - px - (1-p)x^m$$

así, obtenemos la recurrencia

$$S(n,m) - pS(n-1,m) - (1-p)S(n-m) = 0.$$

$$S(n,m) = pS(n-1,m) + (1-p)S(n-m,m).$$ A little checking shows this holds for $n > m$, and we have the initial values $S(n,m) = p^n$ for $n< m$, and $S(m,m) = p^m - p$.

Answer 3

Repeticiones en cadenas: algoritmos y combinatoria