Consultas generales

Hola, quería consultar sobre un concepto que está relacionado con problemas de combinatoria, del cual tengo algunas dudas. Tal vez esto pueda ir para el parcial, entonces me parece mejor preguntarlo antes.

El problema surge en querer contar la cantidad de palabras de largo $n$ que se pueden formar usando las letras ${A,B,C,D}$ pero que no pueden contener más de $c_A$ letras $A$, $c_B$ letras $B$, $c_C$ letras $C$ ni $c_D$ letras $D$. Para ordenar el problema suponemos que la letra $A$ es la que aparece en menor cantidad, luego le sigue la $B$, luego la $C$ y finalmente la $D$, lo que es equivalente a decir que $c_A\leq c_B\leq c_C\leq c_D$.

Comenzando por el caso más fácil, tenemos que $n$ no llega a agotar ninguna letra, por lo que no tenemos restricciones al construir la palabra. Para este caso podríamos plantearnos un problema más sencillo:

Contar la cantidad de palabras de largo n que se pueden formar usando las letras ${A,B,C,D}$.

Debido a que no tenemos limitaciones, la cantidad de palabras posibles sería $4^n$.

Luego le sigue el caso donde $c_A$, es decir que nos vemos limitados a usar la letra $A$ hasta $c_A$ veces. Esto podemos plantearlo como el siguiente problema:

Contar la cantidad de palabras de largo n que se pueden formar usando las letras ${A,B,C,D}$ que no contengan más de $c_A$ letras $A$.

Este problema podemos resolverlo separando en casos y sumando todas las ocurrencias de las palabras que:

• no contengan la letra $A$. Aprovecharemos a utilizar la notación $\#\bar{A}$ para indicar la cantidad de letras de nuestro conjunto que no son $A$, en nuestro caso $\#\bar{A}=3$. Luego, la cantidad de palabras que no contienen la letra $A$ es $(\#\bar{A})^n$.
• contengan sólo una letra $A$. Esto lo podemos ver como querer agregar una letra $A$ en una palabra de largo $n-1$ que solo contenga letras $B$, $C$ o $D$. Si imaginamos $n$ casilleros en donde debemos colocar una letra $A$ y el resto llenarlos con las letras de la palabra que no contiene $A$, podemos decir que tenemos $n$ posibles lugares donde colocar dicha la letra $A$. Por lo tanto tenemos $n.(\#\bar{A})^{n-1}$ posibles palabras donde la letra $A$ aparecerá sólo una vez.
• contengan sólo dos letras $A$. En este caso tendremos que elegir dos lugares entre $n$ disponibles para colocar las letras $A$; tendremos $\binom{n}{2}$ posibilidades para hacerlo. La cantidad de palabras posibles con sólo dos letras $A$ será $\binom{n}{2}(\#\bar{A})^{n-2}$

Así vamos repitiendo el cálculo hasta $c_A$ letras $A$. Entonces la cantidad de palabras que se puedan formar que sólo tengan restricciones en la letra $A$ es igual a $\sum_{k_1=0}^{c_A}\binom{n}{k_1}(\#\bar{A})^{n-k_1}$.

Continuamos con el problema, y ahora tomamos el caso en el que $c_B$, es decir que $n$ agota dos letras de lo que tenemos permitido usar. El problema ahora toma la siguiente forma:

Contar la cantidad de palabras de largo n que se pueden formar usando las letras ${A,B,C,D}$ que no contengan más de $c_A$ letras $A$ ni tampoco más de $c_B$ letras $B$.

De nuevo esto lo podemos enfrentar separando por casos, contando las palabras que:

• no contengan ni $A$ ni $B$
• no contengan $A$ pero contengan una $B$
• no contengan $A$ pero contengan dos $B$

...

• no contengan $A$ pero contengan $c_B$ letras $B$
• contengan una $A$ pero no contengan $B$
• contengan una $A$ y una $B$

...

• contengan $c_A$ letras $A$ y $c_B$ letras $B$ (estos casos podrían ser cero)

Como vemos, son demasiados casos,  tendríamos que construir una tabla que indique cuantas $A$ y cuantas $B$ tiene que tener cada caso y sumar luego todos los casos.

Para el caso donde la palabra no contiene ninguna $A$ pero puede contener $B$ resulta en $\sum_{k_2=0}^{c_B}\binom{n}{k_2}(\#\bar{A}\bar{B})^{n-k_2}$, donde como mencionamos anteriormente $\binom{n}{k_2}$ representa las formas de elegir $k_2$ lugares para $B$ de $n$ disponibles y $(\#\bar{A}\bar{B})^{n-k_2}$ representa las formas de armar palabras de largo $n-k_2$ de forma que no tengan ni $A$ ni $B$.

Ahora, si agregamos la posibilidad de que la palabra pueda contener $A$ obtenemos $\sum_{k_1=0}^{c_A}\sum_{k_2=0}^{c_B}\binom{n}{k_1}\binom{n-k_1}{k_2}(\#\bar{A}\bar{B})^{n-k_1-k_2}$. Notar que los números combinatorios representan las formas de elegir $k_1$ lugares para $A$ de $n$ disponibles y las formas de elegir $k_2$ lugares para $B$ de $n-k_1$ disponibles respectivamente. Como comentario adicional, podemos escribir el resultado también como $\sum_{k_1=0}^{c_A}\binom{n}{k_1}\sum_{k_2=0}^{c_B}\binom{n-k_1}{k_2}(\#\bar{A}\bar{B})^{n-k_1-k_2}$. La idea detrás de esto es algo así como calcular cuantas palabras no tienen ni $A$ ni $B$ y luego contar para cada una de ellas de cuantas maneras podemos entremezclar las letras $A$ y $B$.

Continuamos y ahora pasamos a la restricción del uso de tres letras, cuando $c_C$. El razonamiento es análogo:

$\sum_{k_1=0}^{c_A}\sum_{k_2=0}^{c_B}\sum_{k_3=0}^{c_C}\binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}(\#\bar{A}\bar{B}\bar{C})^{n-k_1-k_2-k_3}$

El producto de los números combinatorios es igual al coeficiente multinomial $\binom{n}{k_1,k_2,k_3,n-k_1-k_2-k_3}$ al cual en realidad denotaremos como ${n \brack k_1,k_2,k_3}$ debido a que no nos interesa tener en cuenta el término $n-k_1-k_2-k_3$.

Notamos que como nuestro conjunto solo tiene cuatro letras, $(\#\bar{A}\bar{B}\bar{C})=1$. Entonces nos queda:

$\sum_{k_1=0}^{c_A}\sum_{k_2=0}^{c_B}\sum_{k_3=0}^{c_C}$${n \brack k_1,k_2,k_3}$

Ahora, la pregunta es la siguiente. ¿Qué pasa cuando el uso de las cuatro letras está restringido? ¿Pasaríamos a usar $(\#\bar{A}\bar{B}\bar{C}\bar{D})$ que sería cero? Es decir, ¿de qué manera podemos contemplar este caso aplicando el mismo razonamiento?

Agradecería su respuesta.

Saludos.