Combinaciones con repetición
Las combinaciones con repetición se parecen a las combinaciones clásicas; solo permitimos que los elementos del conjunto de partida M puedan repetirse.
Definición y fórmula
Empecemos con un ejemplo clásico: entras en una tienda y quieres comprar doce latas de refresco para una excursión. En la estantería tienen en total cuatro sabores distintos. Ahora tienes varias posibilidades para comprar las latas: por ejemplo, puedes comprar 5 de naranja, 2 de limón, 1 de cola y 4 de manzana, o puedes comprar exactamente tres latas de cada sabor. ¿Cuántas posibilidades distintas hay en total de comprar las latas de modo que tengas exactamente doce?
Tenemos, pues, el conjunto de partida M = {naranja, limón, cola, manzana} y nos preguntamos cuántas k-uplas existen, con k = 12, formadas por elementos del conjunto M y en las que no importa el orden.
La deducción de la fórmula es bastante más complicada que en los demás problemas de combinatoria. Primero nos imaginaremos nuestra compra como una sucesión de ceros y unos, de modo que el número de unos corresponde al número de latas compradas de un sabor y el cero separa los distintos sabores. Así, 111011101111101 nos dice que hemos comprado tres de naranja (los tres primeros 1), después tres de limón (0 es el separador, otros tres 1), luego cinco de cola (0 separador y después cinco 1) y por último una de manzana. Todo el principio se muestra en la siguiente figura:
Si quisiéramos comprar 6 de naranja, 4 de limón, 2 de manzana y ninguna de cola, la sucesión tendría este aspecto:
Fíjate en que la longitud de esta sucesión siempre es 15: tiene que haber 12 unos para comprar doce refrescos en total. Y tiene que haber tres separadores para poder separar los cuatro sabores distintos. Queda por calcular cuántas sucesiones de longitud 15 existen que contengan exactamente tres ceros.
Nos basta calcular la colocación de los ceros: en el momento en que repartimos 3 ceros entre los 12 unos, tenemos una combinación válida de refrescos. Dicho de otro modo: tenemos 15 casillas y tenemos que ocupar 3 de ellas con un cero. Las casillas restantes las ocupamos automáticamente con unos.
Esto ya es un problema sencillo de combinaciones sin repetición. Numeramos las 15 casillas con los números {1, …, 15} y de este conjunto elegimos siempre ternas de números, con lo que obtenemos tres índices donde colocar el cero. Por ejemplo, para la combinación {2, 4, 7} obtendríamos la sucesión 101011011111111. En las posiciones 2.ª, 4.ª y 7.ª hay un cero y el resto son unos. Existen, por tanto, en total
formas distintas de repartir los ceros en las 15 casillas y, por consiguiente, también 455 posibilidades distintas de comprar 12 refrescos si tenemos cuatro sabores distintos.
El razonamiento anterior se puede generalizar. Si tenemos un conjunto de elementos M de tamaño n y elegimos de él k-uplas en las que los elementos pueden repetirse, componemos una sucesión de ceros y unos de longitud n + k − 1 (k unos y n − 1 ceros) y averiguamos de cuántas formas podemos colocar los n − 1 ceros, de modo que el número de combinaciones con repetición, que denotamos CRn,k, es igual a
La última transformación nos la hemos podido permitir gracias a las relaciones básicas entre números combinatorios.
Ejercicios resueltos
- ¿De cuántas formas se pueden repartir 20 entradas gratuitas para el estreno de una obra de teatro entre 10 jubiladas? Es un ejemplo de combinaciones con repetición, porque una jubilada puede recibir varias entradas gratuitas, potencialmente todas. Solo tenemos que darnos cuenta bien de qué es n y qué es k. En realidad elegimos combinaciones de 20 elementos entre 10 jubiladas; dicho de otro modo, formamos una sucesión de ceros y unos de longitud 29 que contiene 20 unos y 9 ceros. Así que n = 10, k = 20. Obtenemos el resultado:
Capítulos: Combinatoria, Variaciones, Permutaciones, Combinaciones, Variaciones con repetición, Combinaciones con repetición, ¿Cuántos PIN distintos existen?
