Fórmula para Combinaciones con Reemplazo

Question

Entiendo cómo funcionan las combinaciones y permutaciones (sin reemplazo). También entiendo por qué una permutación de $n$ elementos ordenados $k$ a la vez (con reemplazo) es igual a $n^{k}$. Por mi investigación, he descubierto que el número de combinaciones con reemplazo de $n$ elementos tomados $k$ a la vez se puede expresar como $(\binom{n}{k})$ [esta "doble" conjunto de paréntesis es la notación desarrollada por Richard Stanley para transmitir la idea de combinaciones con reemplazo].

Alternativamente, $(\binom{n}{k})$ = $\binom{n+k-1}{k}$. Esta es una notación más familiar. Desafortunadamente, no he encontrado una explicación clara de por qué la fórmula anterior se aplica a las combinaciones con reemplazo. ¿Podría alguien ser tan amable de explicar cómo se desarrolló esta fórmula?

Answer 1

Una forma útil de pensarlo:

Imagine que tiene $n$ celdas diferentes de izquierda a derecha. Una combinación sin reemplazo de $k$ objetos de $n$ objetos sería equivalente al número de formas en las que estos $k$ objetos pueden ser distribuidos entre las celdas con como máximo un objeto por celda. La clave aquí es que debido al hecho de que no hay reemplazo, solo hay uno o cero objetos en cada celda. Es fácil ver que esto corresponde a una combinación sin reemplazo porque si representamos las celdas ocupadas con un círculo negro y las vacías con uno blanco habría $k$ círculos negros en la fila y $(n-k)$ blancos en la fila, así que las permutaciones de esta fila son precisamente:

$$\frac{n!}{(n-k)!k!}=\binom{n}{k}$$

$$[][x][x][][x](...)[x][]= \bigcirc \bullet \bullet \bigcirc \bullet (...)\bullet \bigcirc $$

Nota aquí que necesariamente $k\leq n$.

Usando la misma analogía para combinaciones con reemplazo, tenemos $k$ objetos que queremos distribuir en estas $n$ celdas pero ahora podemos poner más de un objeto por celda (por lo tanto con reemplazo). También hay que tener en cuenta que no hay límite en $k$ porque si $k>n$ entonces simplemente podemos poner más de un objeto en cada celda. Ahora viene la parte complicada, podemos contar las permutaciones de este conjunto asignando círculos de forma inteligente. Deje que la división entre las celdas sea un círculo blanco y los objetos círculos negros, luego habría $(n-1)$ círculos blancos y $k$ negros. No es tan difícil ver que cada permutación de estos círculos corresponde a una forma diferente de colocar estos $k$ objetos en las $n$ celdas. Tenemos un total de $(n-1)+k$ círculos, $(n-1)$ blancos y $k$ negros, así que el número de permutaciones de esta fila de círculos es precisamente:

$$\frac{(n-1+k)!}{(n-1)!k!}=\binom{n+k-1}{k}$$

$$[][xxxx][xx][][x][(...)][x][]=$$

$$\bigcirc \bullet \bullet \bullet \bullet \bigcirc \bullet \bullet \bigcirc \bigcirc \bullet \bigcirc(...)\bigcirc \bullet \bigcirc $$

Esto no es realmente una forma rigurosa de probarlo pero creo que ilustra bien el concepto. Si desea una explicación un poco más detallada y ejercicios, recomiendo el libro Introducción a la combinatoria publicado por el United Kingdom Mathematics Trust (UKMT) disponible en su página web. Cubre muchos temas interesantes con un enfoque en la resolución de problemas.

Answer 2

http://www.mathsisfun.com/combinatorics/combinations-permutations.html

Primer resultado en Google para 'combinaciones y permutaciones'. Ofrecen una explicación que cualquiera debería poder entender.

Answer 3

Supon que la pregunta es sobre comprar 6 latas de refresco de 4 marcar de refrescos. Por supuesto, hay más de 6 latas de refrescos para cada marca. El número de combinaciones diferentes es $\binom{4+6-1}{6} = 84$.

Piénsalo de esta manera: Si quisieras 2 latas de refresco de las 4 marcas, la segunda lata de refresco puede ser la misma que la primera. Por lo tanto, la razón por la que es $\binom{5}{2}$ es porque una de las opciones de entre las 5 es "duplicado" de refresco. Si fuera $\binom{4}{2}$, no sería combinación con reemplazo.

Por lo tanto, en $\binom{4+6-1}{6}$, el 6-1 refresco (o k-1) es el "duplicado" de refresco lo que significa que puede ser uno de los refrescos que ha sido seleccionado.

Answer 4

He estado buscando la misma respuesta y finalmente encontré algo que pude entender y explicarle a mi hijo de 10 años.

Benjamin & Quinn 2003, p. 71 Por ejemplo, si tienes cuatro tipos de donas (n = 4) en un menú para elegir y quieres tres donas (k = 3), la cantidad de formas de elegir las donas con repetición se puede calcular como

Este resultado se puede verificar enumerando todos los 3-subconjuntos múltiples del conjunto S = {1,2,3,4}. Esto se muestra en la siguiente tabla.

No. 3-Multiconjunto Eq. Solución 1 {1,1,1} [3,0,0,0]
2 {1,1,2} [2,1,0,0]
3 {1,1,3} [2,0,1,0]
4 {1,1,4} [2,0,0,1]
5 {1,2,2} [1,2,0,0]
6 {1,2,3} [1,1,1,0]
7 {1,2,4} [1,1,0,1]
8 {1,3,3} [1,0,2,0]
9 {1,3,4} [1,0,1,1]
10 {1,4,4} [1,0,0,2]
11 {2,2,2} [0,3,0,0]
12 {2,2,3} [0,2,1,0]
13 {2,2,4} [0,2,0,1]
14 {2,3,3} [0,1,2,0]
15 {2,3,4} [0,1,1,1]
16 {2,4,4} [0,1,0,2]
17 {3,3,3} [0,0,3,0]
18 {3,3,4} [0,0,2,1]
19 {3,4,4} [0,0,1,2]
20 {4,4,4} [0,0,0,3]

Answer 5

Teniendo en cuenta un multiconjunto con $n$ tipos distintos de objetos y al menos $k$ de cada tipo, estamos interesados en contar el número de submulticonjuntos de tamaño $k$. Si tenemos $x_i$ elementos del $i^{th}$ tipo, entonces el número de ese multiconjunto corresponde al número de soluciones enteras no negativas de $x_1 + x_2 + \cdots x_n = k$, y eso es $\binom{n+k-1}{k}$. Para ver que esta formulación tiene sentido, considerando el ejemplo de submulticonjuntos de tamaño 3 tomados del multiconjunto con 4 tipos proporcionado por HKA, note que las sumas de las entradas entre corchetes, que cuentan el número de repeticiones de cada tipo de elemento, todas suman 3. El otro argumento, proporcionado por braham_snyder, empleando el llenado de cubos definido por los espacios entre separadores, se puede usar para demostrar que el número de soluciones enteras no negativas de la suma de $x_i$s igual a $k$ es la misma expresión, esencialmente tiene $k$ unos que necesita distribuir entre $n$ contenedores, permitiendo que algunos contenedores contengan ninguno. Los $x_i$s cuentan el número de unos en el contenedor $i^{th}$.