¿Cuántas cadenas contienen todas las letras del alfabeto?

Question

Dado un alfabeto de tamaño $n$ cuántas cadenas de longitud $c$ contienen todas las letras del alfabeto al menos una vez?

Primero intenté utilizar una relación de recurrencia para resolverlo:

$$ T(c) = \left\{ \begin{array}{cr} 0 &\mbox{ if $c<n$} \\ n! &\mbox{ if $c = n$} \\ T(c-1) \cdot n \cdot c &\mbox{ if $c > n$} \end{array} \right. $$

Como no hay cadenas que contengan todas las letras si c < n, y si c = n entonces son todas las permutaciones. Cuando c > n se puede tomar cualquier cadena de tamaño (c-1) que contenga todas las letras (de las cuales hay $T(c-1)$ para elegir), usted elige qué letra añadir (de las que hay $n$ opciones) y hay $c$ diferentes posiciones para ponerlo. Sin embargo, esto da resultados mayores que $n^c$ (el número total de cadenas), así que no puede ser correcto, y me di cuenta de que era porque se podían contar algunas cadenas varias veces, ya que se pueden hacer tomando diferentes pasos de inserción.

Entonces pensé en ser más simple: eliges n posiciones en la cadena, pones cada letra del alfabeto en una de esas posiciones, y luego dejas que el resto de la cadena sea cualquier cosa:

$$ {c\choose{n}} \cdot n! \cdot n^{c-n} $$

Pero, de nuevo, esto cuenta cuerdas múltiples veces.

También he considerado la posibilidad de utilizar coeficientes multinomiales, pero como no sabemos cuántas veces aparece cada letra en la cadena, parece poco probable que sean de gran ayuda. También he probado otros métodos, algunos complicados y otros sencillos, pero ninguno parece funcionar.

¿Cómo se podría elaborar una fórmula para esto? Seguro que hay algo sencillo que se me escapa.

Answer 1

Dejemos que $W(c,n)$ denotan el número de palabras de longitud $c$ de un alfabeto de $n$ cartas. A continuación, $W(c,n)=n^c$ .

De ellas, el número de palabras del mismo tamaño que no contienen una de las letras es $W(c,n-1)=(n-1)^c$ . El número de formas de elegir qué letra falta es $\binom{n}{1}$ .

El número de palabras del mismo tamaño que no contienen dos letras es $W(c,n-2)=(n-2)^c$ . El número de formas de elegir qué dos letras faltan es $\binom{n}{2}$ ... y así sucesivamente ...

Ahora utilizamos el principio de inclusión-exclusión: (resta el número de palabras a las que les falta una de las letras, luego añade el número al que le faltan dos de las letras, resta el número al que le faltan tres de las letras,...)

Lo conseguimos:

$$W(c,n)-\binom{n}{1}W(c,n-1)+\binom{n}{2}W(c,n-2)-\binom{n}{3}W(c,n-3)+\cdots+(-1)^{n-1}\binom{n}{n-1}W(c,n-(n-1)).$$

Esto es

$$n^c-\binom{n}{1}(n-1)^c+\binom{n}{2}(n-2)^c-\binom{n}{3}(n-3)^c+\cdots+(-1)^{n-1}\binom{n}{n-1}1^c.$$

o

$$\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}(n-k)^c.$$

Otra forma podría ser: Denote $S_c^n$ el número de maneras de dividir la palabra de longitud $c$ en $n$ piezas. Entonces sólo tenemos que elegir qué letra va a cada una de las $n$ piezas. Este número es $n!$ . Así que el número de palabras que buscamos es

$$n!S_c^n.$$

Las cifras $S_c^n$ se llaman números de Stirling del segundo tipo.

Answer 2

Como has dicho, no hay soluciones si c<=n.

entonces todos los resultados contendrán todos los n cartas y c-n letras al azar por lo que las combinaciones son:

((c-n).n)

Pero las cadenas tienen posiciones fijas, así que necesitamos todas las permutaciones fuera de esto:

((c-n).n).c!

Para cada carácter (c-n) hay posibles duplicados de letras para los que el ordenamiento no mide, por lo que hay que dividir a eso.

((c-n).n).c!/ (c-n)! //not sure if this is correct

Esto es sólo una línea de razonamiento que espero que te lleve más lejos, no estoy seguro de que todo sea correcto.