Lo que estamos buscando es, dado A un alfabeto de tamaño k, la cantidad de cadenas de tamaño n que contienen exactamente m símbolos de A.

Para resolver este problema primero vamos a resolver lo siguiente:

Cuantas cadenas de tamaño n pueden ser creadas con todos los símbolos de un alfabeto de k símbolos?

Se propone la siguiente relación de recurrencia de 2 variables, donde:

n: representa el tamaño de la cadena

k: representa la cantidad de símbolos en el alfabeto

f(0, k) = 0

Para todo k, ya que la cantidad de cadenas de tamaño 0 que pueden formarse con todos los símbolos de A es 0.

f(1, 1) = 1

Ya que existe solo una cadena de tamaño 1 con 1 símbolo.

f(n, k) = k( f(n-1,k) + f(n-1, k-1) )

Demostración

Llamemos An,k al conjunto de todas las cadenas de tamaño n que contienen a todos los símbolos de A e intentemos construir todas las cadenas que pertenecen a este conjunto.

Para cada símbolo a de An,k vamos a realizar el siguiente procedimiento:

1. Llamemos An-1,k al conjunto de todas las cadenas de tamaño (n-1) con exactamente k símbolos de A (o sea con todos los símbolos de A).

Para cada cadena α de An-1,k construimos una nueva cadena concatenandole a, nos queda así una nueva cadena: . Como α tiene tamaño (n-1), la nueva cadena tiene tamaño n.

Ademas por definición de An-1,k, α contiene a todos los símbolos de A, y en particular contiene a a. Entonces de esta manera hemos formado todas las cadenas de An,k que comienzan por a y tienen al menos 2 ocurrencias de a.

Nos queda todavía construir todas las cadenas de An,k que comienzan por a pero tienen solo una ocurrencia de a.

2. Llamemos An-1,k-1 al conjunto de todas las cadenas de tamaño (n-1) que están formadas por todos los símbolos de A menos a.

Para cada cadena β de An-1,k-1 construimos una nueva cadena . Se cumple entonces que tiene tamaño n y ademas dado que β contiene a todos los símbolos de A menos a a y le hemos concatenado a, contiene los k símbolos de A.

A partir de estos dos pasos hemos construido todas las cadenas de An,k que comienzan con a. Como por definición de An,k, cualquier cadena de An,k necesariamente tiene que comenzar con un símbolo de A y a es un elemento arbitrario podemos aplicar el procedimiento para construir todas las cadenas del conjunto An,k.

Como por hipótesis, |An-1,k-1| = f(n-1,k-1), |An-1,k| = f(n-1,k) y como existen exactamente k símbolos de A se cumple que f(n, k) = k( f(n-1,k) + f(n-1, k-1) ).

Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Asumiendo que la función anterior es correcta, podemos proponer la siguiente función:


g

(
n
,
m
,
k
)

=

(

m
k

)

×
f

(
n
,
m
)


Llamemos Am al conjunto de todos los subconjuntos de A con exactamente m elementos. Es conocido que la cantidad de subconjuntos de tamaño m de un conjunto se puede calcular como:


|

A
m

|
=

(

m
k

)


(Ver Combination) . Sabemos ademas por el resultado anterior que la cantidad de cadenas de tamaño n que pueden hacerse de un conjunto de tamaño m es igual a f(n,m), a partir de lo cual derivamos la formula.