Combinación con repeticiones.

Question

La fórmula para calcular una combinación k con repeticiones de n elementos es: $$\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}$$

Me gustaría si alguien puede darme una prueba básica sencilla que un principiante pueda entender fácilmente.

Answer 1

Este problema tiene muchos nombres -estrellas y rayas, bolas y urnas-, pero básicamente se trata de cómo distribuir $n$ objetos (los llamamos "bolas") en $k$ categorías (las llamamos "urnas"). Podemos pensar en ello de la siguiente manera.

Toma $n$ bolas y $k-1$ separadores. Si una bola cae entre dos divisores, va a la urna correspondiente. Si no hay nada entre dos divisores, entonces no hay nada en la urna correspondiente. Veamos esto con un ejemplo concreto.

Quiero distribuir $5$ bolas en $3$ urnas. Como antes, tome $5$ bolas y $2$ divisores. Visualmente:

|ooo|oo

En este orden, no tendríamos nada en la primera urna, tres en la segunda y dos bolas en la tercera. La pregunta entonces es ¿de cuántas maneras podemos disponer estas 5 bolas y dos separadores? Claramente: $\dfrac{(5+3-1)!}{5!(3-1)!} = \displaystyle {7 \choose 2} = {7 \choose 5}$ .

Tenemos que hay $\dfrac{(n+(k-1))!}{(k-1)! n!}$ el $n$ bolas y $k-1$ divisores (ya que las bolas no son distintas entre sí y los divisores no son distintos entre sí). Obsérvese que esto es igual a $\displaystyle {n+k-1 \choose k-1} = {n + k - 1 \choose n}$ .

Answer 2

Bien, supongamos que dibujo (con sustitución) $k$ artículos de la $n$ y los anoto en una hoja de puntuaciones que tiene este aspecto, poniendo una X en la columna correspondiente cada vez que saco un elemento.

El resultado será $k$ Xs, separadas por ( $n-1$ ) barras verticales. Contando las Xs y las barras verticales juntas es $k+n-1$ artículos. Y lo que he dibujado está totalmente determinado por cuál de esos $k+n-1$ son las X.

Esto es claramente $\binom{k+n-1}{k}$ .

Answer 3

Básicamente $$\binom {a+b}{a} = \binom {a+b}{b} = \frac {(a+b)!}{a!b!}$$

porque el número de formas de elegir $a$ artículos de $a+b$ es el mismo que el número de formas de elegir el $b$ elementos a excluir para que $a$ son sobrantes. La fórmula es simétrica en $a$ y $b$ .

Answer 4

Las barras de separación se añaden al problema aunque no estén ahí; son imaginarias.

Esto es un poco pensar fuera de la caja, pero también podría ser confuso cuando no hay una conexión real con el problema.

A veces es más fácil guiarse por un ejemplo primero y hacer una abstracción después. Hagamos el caso $n=3,k=3$ con y sin los separadores y, con suerte, los separadores imaginarios encontrarán un lugar real para ellos después.

Supongamos que tenemos tres tipos de frutas disponibles y estamos recogiendo tres frutas en total donde se permite la repetición. Que las frutas sean manzanas, naranjas y plátanos. Entonces las opciones (sin separadores) son :

aaa,aao,aab,aob,aoo,abb,oob,obb,ooo,bbb.

Vamos a reescribirlos con los separadores:

aaa//,aa/o/,aa//b,a/o/b,a/oo/,a//bb,/oo/b,/o/bb,/ooo/,//bbb.

En la primera línea los separadores son imaginarios, es decir, no están ahí; en la segunda línea están ahí, es decir, son reales. Entonces, ¿cuál es la diferencia? ¿Por qué es más útil tenerlos? Bueno, la segunda línea responde a una pregunta que resulta ser también la respuesta a nuestra pregunta. Piensa en una cadena de bits donde los separadores son 1's y los frutos son 0's. La pregunta a la que responde la segunda línea es "¿cuántas formas hay de tener exactamente dos 1's en una cadena de bits de 5?"

Entonces, ¿cuál es la conexión?

Esta es la situación. Has repartido las frutas (sin separadores) pero no sabes cómo contarlas. Alguien te dice que si echas separadores el problema se convierte en una pregunta de cadena de bits con cierto número de 1's en ella. Entonces accedes a imaginártelos porque así se resuelve el problema.

Answer 5

Suponga que tiene $n+k-1$ distintas bolas y dos bolsas. Ahora quieres elegir $k$ bolas y ponerlas en la bolsa $1$ y el resto $n-1$ bolas en la bolsa $2$ .

Si eliges $k$ bolas primero, hay $\binom{n + k - 1}{k}$ posibles formas de hacerlo. Por otro lado, puedes pensar que estás escogiendo $n-1$ bolas primero y ponerlas en la bolsa $2$ y el resto $k$ bolas en la bolsa $1$ . Estos dos métodos deberían ser equivalentes (eligiendo $k$ bolas para la bolsa $1$ es lo mismo que elegir $n-1$ otras bolas para la bolsa $2$ ). Por lo tanto, $\binom{n + k - 1}{k}=\binom{n + k - 1}{n-1}$ .