Argumentos básicos de conteo 6 (conteo con repetición)

Versión para impresión

Introducción: conteo con repetición

Hasta ahora hemos visto permutaciones, variaciones y combinaciones. Corresponden, respectivamente,  a ordenar en todas las formas posibles los elementos de un conjunto $\{1,2,\ldots,n\}$, subconjuntos de tamaño r ordenados de todas las formas posibles, subconjuntos de tamaño r. Ahora vamos a ver qué pasa si los elementos del conjunto $\{1,2,\ldots,n\}$ tienen copias y se puede elegir más de una de cada elemento. Ejemplos: las letras de un alfabeto al formar palabras, panes en la panadería (biscochos, cuernos, chilindrinas, conchas, campechanas, bolillos, bollos, donas, teleras, hojaldrados, cielos,...), consumibles para la PC (cartuchos para impresora,  papel para impresora, CD's, DVD's, gas quitapolvo, espuma limpiapantalla,...).

Variaciones con repetición

El modelo de conteo que permite obtener copias de un mismo objeto, y en el cual el orden es importante, es el de la urna con los n objetos distintos (representados por bolas numeradas), acompañado de la extracción con reemplazo: cada vez que se hace una extracción, el objeto extraído se reemplaza (es decir, se vuelve a poner en la urna). El ejemplo prototipo de una r-variación con repetición son las r-palabras con letrs de un alfabeto de tamaño n. Por ejemplo las 2-variaciones de los objetos A,B,C son AA, AB,AC,BA,BC,CA,CB,CC. Se trata de las 2-palabras con letras del alfabeto A,B,C. (En la urna están las letras A,B,C y se hacen dos extracciones con reemplazo.)

En general, si se quieren contar las r-variaciones con repetición (r-palabras) de n objetos (alfabeto de n letras), su número es $n^r$. Pues cada objeto en la urna tiene n posibilidades de ser elegido (cada letra se puede elegir de n maneras) en cada elección (posición) --y son r elecciones. (De más está decir que se aplica el principio multiplicativo.)

Permutaciones con repetición

A diferencia de las variaciones con repetición, en las que el número de copias de cada objeto es irrestricto, en las permutaciones con repetición se restringe el número de copias de cada objeto. Por esta razón el modelo básico es una urna que tiene en su interior el número de copias estipuladas (pre-especificadas) para cada tipo de objeto. Es común que cada tipo de objeto se represente con un color, de tal manera que en la urna hay $r_1$ bolas de un color, $r_2$ de otro color, etc. --donde $r_1$  es el número de copias del objeto del primer tipo que deben estar presentes en la permutación, $r_2$ el número estipulado para el objeto del segundo tipo, etc. Aclaremos la idea con

Un ejemplo

¿Cuántas palabras de longitud 10 se pueden formar con las letras A,B,C, con la condición de que la A aparezca 2 veces, la B 3, y la C 5?

Solución

Para resolver este problema con el modelo de urna se usa el siguiente

Artificio cognitivo 1

Las 2 bolas azules (representando dos copias de la A) se etiquetan con 1 y 2, las blancas con 3,4, 5 y las 5 de color café con 6,7,8,9,10. De esta manera podemos ver las 10 bolas de la urna de dos formas: como 10 diferentes (si atendemos a su etiqueta o, alternativamente, como representantes de las tres clases si atendemos a su color. Si atendemos a su etiqueta (su número adherido) y las extraemos las 10 en sucesión sin reemplazo, las posibilidades de extracción son las 10! permutaciones sin repetición (los 10 números adheridos en todos los órdenes posibles).

Ahora imaginemos que tenemos lsa 10! ordenaciones en una lista y las clasificamos en tres clases atendiendo a su color. Por ejemplo, la permutación 12345678910 es indistinguible, atendiendo al color, de --por ejemplo-- la permutación 21543109876. Denotemos con $P(10;2,3,5)$ el número buscado de permutaciones con repetición. Entonces, por cada una de ellas, hay 2!3!5! permutaciones --atendiendo a los números adheridos--; pero esas 2!3!5! permutaciones son indistinguibles si se atiende a su color.

De esta manera, hemos contado de dos formas las permutaciones sin repetición (los elementos de un mismo conjunto) y ello nos permite establecer la ecuación que nos lleva a la fórmula de las combinaciones con repetición: $2!3!5!P(10;2,3,5)=10!$

El razonamiento del ejemplo es fácilmente generalizable. El lector no hallará grandes dificultades para convencerse de que el número de r-permutaciones con repetición --donde hay $r_1$ objetos de tipo 1, $r_2$ del tipo 2, etc. y $r=r_1+r_2+...$--,  está dado por la fórmula $P(r;r_1,r_2,...)=r!/[(r_1)!(r_2)!...].$

Argumento alternativo (artificio cognitivo 2)

Otra forma de razonar el problema es imaginando las posiciones de las 10 letras de la 10-palabra (como slots en espera de ser llenados), y elegimos en sucesión las posiciones de la A, las de la B y las de la C. Para la A tenemos que elegir 2 posiciones de entre las 10; para la B ya solamente quedan 8 posiciones de entre las cuales elegimos 3; finalmente, para la C no hay necesidad de elegir pues tenemos que elegir 5 de entre las 5 restantes. De esta manera, $$P(10;2,3,5)=C(10,2)C(8,3)C(5,5).$$

Se deja como ejercicio para el lector el convencerse de que este número es el mismo que $P(10;2,3,5)=10!/[2!3!5!].$ obtenido antes.  Como ejercicio también se deja al lector la generalización del argumento para obtener la forma alternativa de obtener las r-permutaciones con repetición donde hay $r_i$ objetos del tipo $i$ ($i=1,2,...,n$) y $r=r_1+r_2+...,r_n.$  Es decir, la fórmula $P(r;r_1,r_2,...)=C(r,r_1)C(r-r_1,r_2)...C(r_n,r_n).$

Combinaciones con repetición

Dado un conjunto $\{1,2,\ldots,n\}$ de (clases) de objetos, queremos elegir r de ellos con repeticiones permitidas. Por ejemplo, vamos a la panadería y queremos comprar 10 panes, a elegir entre bollos, cuernos, chilindrinas. En estos casos (a diferencia de las palabras en un alfabeto) no interesa el orden de los objetos sino solamente el número de cada tipo. (De cada tipo de objeto hay copias suficientes para satisfacer nuestras necesidades.)  El problema de las combinaciones con repetición es entonces:

¿De cuántas formas se pueden elegir r objetos de entre n tipos, con repeticiones permitidas?

Modelo diofantino


En este problema, el modelo de urna no es adecuado. Por esta razón tratemos de modelarlo de otra manera. Lo primero que debemos observar es que de cada tipo podemos elegir cualquier número de copias con tal de que en total se elijan r. Esto permite modelar con (o transformar el problema a) la ecuación diofantina $x_1+x_2+...+x_n=r$ --en donde se trataría de contar todas las soluciones para las $x_i$ en enteros no negativos.

Y aunque todavía no sepamos cómo resolver esta diofantina, el modelo nos proporciona un objeto más concreto sobre el cual razonar. Por ejemplo, podemos razonarlo para valores pequeños de n y r. Si n=2 (dos tipos de objetos) y r=5 (elección de 5 objetos) el problema parece no presentar ninguna dificultad. Por ejemplo si son peras y manzanas y queremos elegir 5 frutas, es claro que al elegir el número de manzanas, el de las peras queda determinado. Las soluciones posibles son 6: 05,14,23,32,41,50.

Modelo de separadores

En un grado mayor de abstracción podemos representar las 5 frutas con fichas o bolas e imaginarlas en una línea, una después de la otra. Para hacer la distribución de los dos tipos de objeto colocamos un separador entre las bolas: a la izquierda del separador quedarían las peras, a la derecha las manzanas. (El lector puede imaginar que el separador tiene poderes mágicos: convierte las fichas en fruta.) Este dispositivo de conteo es un legado cultural y se llama método de los separadores. (El separador se puede colocar al principio o al final --o entre dos consecutivos-- dado que la elección de ninguna manzana o ninguna pera es permitida; de esta manera hay 6 lugares en que se pouede colocar el separador.

En general, el número de formas en que se pueden elegir r objetos de entre n tipos, con repeticiones permitidas, se resuelve imaginando $n+r-1$ posiciones en los que se van a colocar r bolas y n-1 separadores (dado que bastan n-1 separadores para lograr la clasificación, y la distribución de los r objetos en n clases). Entonces, se eligen $n-1$  lugares de entre los $n+r-1$ disponibles para colocar los separadores. Hay entonces $C(n+r-1, n-1)$ formas de elegir r objetos de entre n tipos, con repeticiones permitidas.

Solución de la diofantina

Con la idea de los separadores uno puede asociar en la ecuación diofantina los $n-1$ signos + como separadores. Con la salvedad de que esto resuelve un problema asociado diferente: el número de soluciones enteras positivas a la ecuación $x_1+x_2+...+x_n=r.$  Porque uno puede imaginar el número r como r unos en alineados uno después del otro, y entonces elegir $n-1$ lugares intermedios entre los r-1 disponibles para colocar el signo más. Este razonamiento da lugar a la fórmula C(r-1,n-1) para el número de soluciones en enteros positivos de la ecuación $ x_1+x_2+...+x_n=r.$  Y también para el número de formas de elegir r objetos de n tipos con repeticiones permitidas --pero con la condición de tomar al menos uno de cada tipo.

Y de esta solución particular ya podemos pasar al caso general. Porque podemos hacer el cambio de variable $x'_i=x_i+1$,  para incluir las posibles soluciones en que ninguna copia del tipo $i$ se escoge. Porque si sumamos n de cada lado de la ecuación $x_1+x_2+...+x_n=r$, se obtiene $x_1+1+x_2+1+...+x_n+1=n+r$. Pero ahora cada una de las variables $ x'_i=x_i+1$ es positiva --y la $x_i$ ahora podría tomar el valor cero. Este artificio de sumar la misma cantidad en cada lado de la ecuación hace el truco de resolver el problema general de soluciones no negativas a partir del caso particular de soluciones positivas. Porque aplicando la misma idea de antes, podemos imaginar $n+r$ unos alineados e introducir $n-1$ signos más entre los $n+r-1$ lugares disponibles. Es decir, el número de soluciones no negativas de la ecuación diofantina $ x_1+x_2+...+x_n=r$ es $C(n+r-1, n-1)$. Y también es la solución al problema de elegir r objetos de entre n tipos con repeticiones permitidas.

Instancias de uso

 

Instancia 1

¿Cuántos términos tiene la expansión de $(a + b + c)^{20}$?

Solución

Cada uno de los términos es de la forma $Aa^xb^yc^z$ (A es el coeficiente y no nos interesa cuál sea) con $x+y+z=20$. De aquí que se trata del problema de elegir $r=20$ objetps de $n=3$ tipos, con repeticiones permitidas. Y ya sabemos que hay $C(3+20-1,2)=C(22,2)=231$ formas.

Instancia 2

Calcular el coeficiente de $a^{10}b^3c^7$ en la expansión de $(a + b + c)^{20}$

Solución

Para lograr $a^{10}b^3c^7$ en la expansión de $(a + b + c)^{20}$ hay que elegir 10 paréntesis de donde se toma la $a$, 3 de donde se toma la $b$ y 7 de donde se toma la $c$. Y ya sabemos que las formas de hacer esto son $C(20,10)C(10,3)C(7,7)$, es decir, el número de las 20-permutaciones con repetición, con 10 de un tipo, 3 de otro y 7 de un tercer tipo.

Instancia 3

Abro el refrigerador. Veo latas de jugo, cerveza, coca cola, gatorade. Tengo tanta sed que elijo tres latas. ¿De cuántas formas puedo hacerlo?

Solución:  Se deja al lector

(Continuará con problemas de distribución de bolas en cajas)