5.1: Repetición ilimitada

Para muchos propósitos prácticos, aunque el número de elementos indistinguibles en cada clase no sea realmente infinito, estaremos dibujando un número lo suficientemente pequeño como para que no se nos acabe. La tienda de bagels que visitamos en el Ejemplo 2.2.1 no es probable que se quede sin una variedad de bagel antes de llenar un pedido en particular. En los juegos de cartas estándar, nunca repartimos suficientes cartas a un solo jugador para que pueda tener todas las cartas de un palo y aún así estar recibiendo más cartas.

Este es el tipo de escenario que vamos a estudiar en esta sección. La configuración que usaremos es asumir que hay\(n\) diferentes “tipos” de artículo, y hay suficientes artículos de cada tipo que no nos quedaremos sin. Luego elegiremos artículos, permitiéndonos elegir repetidamente artículos del mismo tipo tantas veces como queramos, hasta que el número total de artículos que hemos elegido sea\(r\). Observe que (a diferencia del Capítulo 3), en este escenario\(r\) podrá rebasar\(n\).

Consideraremos dos escenarios: el orden en el que hacemos la elección importa, o el orden en el que hacemos la elección no importa.

Ejemplo\(\PageIndex{1}\)

Chris ha prometido traer de vuelta bagels para tres amigos con los que está estudiando (así como uno para él mismo). En la tienda de bagels se venden ocho variedades de bagel. ¿De cuántas maneras puede elegir los bagels para regalar a Jan, Tom, Olive y a él mismo?

Solución

Aquí, importa quién obtenga qué bagel. Podemos modelar esto asumiendo que el primer bagel que Chris ordene será para él, el segundo para Jan, el tercero para Tom y el último para Olive. Así, importa el orden en que pide los bagels.

De hecho vimos de nuevo en el Capítulo 2 cómo resolver este problema. ¡Es solo una aplicación de la regla del producto! Chris tiene ocho opciones para el primer bagel; para cada uno de estos, tiene ocho opciones para el segundo bagel; para cada uno de estos, tiene ocho opciones para el tercer bagel; y para cada uno de estos, tiene ocho opciones para el cuarto bagel. Entonces en total, tiene\(8^4\) formas de elegir los bagels.

Bien, entonces si importa el orden en el que hacemos la elección, solo usamos la regla de multiplicación. ¿Y si el orden no importa?

Ejemplo\(\PageIndex{2}\)

Cuando Chris trajo de vuelta los bagels, resultó que había hecho un mal trabajo al averiguar qué querían sus amigos. Todos negociaban alrededor. Más tarde esa noche, lo mandaron a la tienda de donas, pero esta vez le dijeron que solo trajera ocho donas y se darían cuenta de quién debía obtener cuál. Si la tienda de donas tiene cinco variedades, ¿cuántas formas hay para que Chris llene este pedido?

Solución

Llamemos a las cinco variedades chocolate, arce, crema de Boston, en polvo y jamfilled. Una forma de describir el orden de Chris sería hacer una lista en la que primero escribimos uno\(c\) para cada donas de chocolate, luego uno\(m\) para cada donas de arce, luego uno\(b\) para cada donas de crema Boston, luego uno\(p\) para cada donas en polvo, y finalmente uno\(j\) por cada mermelada -donas rellenas. Ya que Chris está ordenando ocho donas, habrá ocho letras en esta lista. Observe que hay más información proporcionada por esta lista de la que realmente necesitamos. Sabemos que todo el primer grupo de letras son\(c\) s, así que en lugar de escribirlas todas, podríamos simplemente poner un marcador divisorio después de todas las\(c\) s y antes de la primera\(m\). Del mismo modo, podemos poner tres marcadores divisorios más para separar la\(m\)\(b\) s de la\(b\) s, la\(p\) s de la\(p\) s, y la\(j\) s de la s. Ahora tenemos una lista que podría verse algo así:

\(cc||bbb|ppp\)

(Observe en esta posible lista, Chris no eligió donas de arce o mermeladas.)

Ahora bien, en realidad no necesitamos anotar las letras\(c\),\(m\),\(b\), y así sucesivamente, siempre y cuando sepamos cuántos espacios ocupan; sabemos que cualquier letra que aparezca antes del primer marcador divisorio\(c\) es s, por ejemplo. Así, la siguiente lista nos da la misma información que la lista anterior:

_ _||_ _ _|_ _ _|

Del mismo modo, si vemos la lista

|_ _|_ _|_ _ _|_

entendemos que Chris no ordenó donas de chocolate; dos donas de arce; dos donas de crema de Boston; tres donas en polvo; y una rosca rellena de mermelada.

Entonces, un problema equivalente es contar el número de formas de disponer ocho subrayados y cuatro marcadores divisorios en una línea. ¡Esto es algo que ya entendemos! Tenemos doce posiciones que necesitamos llenar, y el problema es: de cuántas maneras podemos llenar ocho de las doce posiciones con subrayados (colocando marcadores divisorios en las otras cuatro posiciones). Sabemos que esto se puede hacer de\(\binom{12}{8}\) maneras.

Esta técnica puede ser utilizada para darnos una fórmula general para contar el número de formas de elegir\(r\) objetos a partir de\(n\) tipos de objetos, donde se nos permite elegir repetidamente objetos del mismo tipo.

Teorema\(\PageIndex{1}\)

El número de formas de elegir\(r\) objetos de\(n\) tipos de objetos (con reemplazo o repetición permitidos) es

\[\binom{n + r -1}{r}\]

Prueba

Utilizamos la misma idea que en la solución al Ejemplo 5.1.2, anterior. Dado que existen\(n\) diferentes tipos de objetos, necesitaremos marcadores\(n − 1\) divisorios para mantenerlos separados. Ya que estamos eligiendo\(r\) objetos, necesitaremos\(r\) subrayados, para cubrir un total de\(n + r − 1\) posiciones. Podemos elegir las\(r\) posiciones en las que los objetos irán por\(\binom{n+r−1}{r}\) caminos, y luego (en cada caso) poner marcadores divisorios en\(n − 1\) las posiciones restantes. Así, hay\(\binom{n+r−1}{r}\) formas de elegir\(r\) objetos de\(n\) tipos de objetos, si se permite la repetición o sustitución de elecciones.

Nuevamente, vamos a querer tener una forma corta para este valor.

Nota

Usamos\((\binom{n}{r})\) para denotar el número de formas de elegir\(r\) objetos de\(n\) tipos de objetos (con reemplazo o repetición permitida),

\[\left(\binom{n}{r} \right) = \binom{n + r - 1}{r}\]

La razón por la que decimos “reemplazo o repetición” es porque existe otro modelo natural para este tipo de problemas. Supongamos que en lugar de elegir ocho bagels de cinco variedades, se le pide a Chris que ponga su mano en una bolsa que contenga cinco guijarros de diferentes colores, y que saque uno; luego lo reemplace, repetidamente (con ocho sorteos en total). Si mantiene la cuenta de cuántas veces dibuja cada una de las rocas, el número de posibles recuentos con los que terminará es exactamente el mismo que el número de órdenes de donas en el Ejemplo 5.1.2.

La siguiente tabla resume algunas de las cosas clave que hemos aprendido sobre el conteo hasta ahora:

Tabla 5.1.1: El número de formas de elegir\(r\) objetos de\(n\) objetos (o tipos de objetos)
\ (r\) objetos de\(n\) objetos (o tipos de objetos) ">	repetición permitida	repetición no permitida
\ (r\) objetos de\(n\) objetos (o tipos de objetos) "> asuntos de orden	\(n^r\)	\(\dfrac{n!}{(n-r)!}\)
\ (r\) objetos de\(n\) objetos (o tipos de objetos) "> el orden no importa	\((\binom{n}{r})\)	\(\binom{n}{r}\)

Ejercicio\(\PageIndex{1}\)

Evaluar los siguientes problemas.

1. Cada una de las diez secciones de tu banda comunitaria (trombones, flautas, etc.) incluye al menos cuatro personas. El director necesita un cuarteto para tocar en un evento escolar. ¿Cuántos juegos diferentes de instrumentos podrían terminar tocando en el evento?
2. El cubo de premios en una feria local contiene seis tipos de premios. Kim gana\(4\) premios; Jordan gana tres premios y Finn gana seis. Cada uno de los niños planea darle uno de los premios que ha ganado a su maestro, y quedarse con el resto. ¿De cuántas maneras se pueden elegir sus premios (incluyendo los regalos al maestro)? (Es importante qué regalo proviene de qué niño.)
3. Hay tres categorías de edad en la feria local de ciencias: junior, intermedio y senior. Los jueces pueden elegir nueve proyectos en total para avanzar al siguiente nivel de competencia, y deben elegir al menos un proyecto de cada grupo de edad. ¿De cuántas maneras se pueden distribuir los proyectos que avanzan entre los grupos de edad?

Ejercicio\(\PageIndex{2}\)

Demostrar las siguientes identidades combinatorias:

1. Para\(k\),\(n ≥ 1\),\((\binom{n}{k}) = (\binom{n-1}{k}) + (\binom{n}{k-1})\).
2. Para\(k\),\(n ≥ 1\),\((\binom{n}{k}) = \binom{n+k−1}{k}\).
3. Para\(k\),\(n ≥ 1\),\((\binom{k+1}{n-1}) = \binom{n+k−1}{k}\).
4. Para\(1 ≤ n ≤ k\),\((\binom{n}{k-1}) = \binom{k-1}{k-n}\).

Ejercicio\(\PageIndex{3}\)

Resolver los siguientes problemas.

1. Encuentra el número de\(5\) -listas de la forma\((x_1, x_2, x_3, x_4, x_5)\), donde cada una\(x_i\) es un entero no negativo y\(x_1 + x_2 + x_3 + x_4 + 3x_5 = 12\).
2. Compraremos\(3\) pasteles (no necesariamente todos diferentes) en una tienda que venda\(4\) tipos de pastel. ¿Cuántos pedidos diferentes son posibles? Enumere todas las posibilidades (usar\(A\) para manzana,\(B\) para arándano,\(C\) para cereza y\(D\) para la otra).
3. Supongamos que las bolas de Lacrosse vienen en\(3\) colores: rojo, amarillo y azul. ¿Cuántas combinaciones diferentes de colores son posibles en un\(6\) paquete de bolas de Lacrosse?
4. Después de expandir\((a + b + c + d)^7\) y combinar términos similares, ¿cuántos términos hay? [Justifica tu respuesta sin realizar la expansión.