Cómo colocar $k$ objetos en $P$ cajas, de modo que puedan colocarse muchos objetos en una caja

Question

Dado $P$ cajas, ¿cuántas maneras hay de colocar $k$ objetos indistinguibles, $k\leq P,$ mediante el cual puede colocar desde $0$ hasta $k$ objetos en cada contenedor. El resultado debe ser $C^{k+P-1}_{k},$ que eventualmente puedo probar por inducción.

Lo que no entiendo es la forma en que se establece este resultado. Puede alguien dar una explicación para derivar el resultado?

Muchas gracias.

Answer 1

Sea $x_i$ sea el número de objetos de la caja $i$ con $i=1,\dots ,P$ . Entonces tenemos que contar el número de no negativo soluciones enteras, es decir $x_i\geq 0$ de $$x_1+x_2+\dots+x_{P-1}+x_P=k.$$ Que es lo mismo (véase Estrellas y barras Tm 2 ) para colocar $P-1$ bares $|$ que divide una secuencia de $k+P-1$ estrellas $\underbrace{\star\star\dots \star\star}_{k+P-1}$ en $P$ bloques: $$ \binom{k+P-1}{P-1}=\binom{k+P-1}{k}.$$ Un razonamiento similar funciona cuando tenemos que contar el número de positivo soluciones enteras, es decir $x_i\geq 1$ (véase Estrellas y barras Tm 1 ) que viene dada por $$\binom{k-1}{P-1}.$$

P.D. Recomiendo también el vídeo de Numberphile Estrellas y barras (y panecillos) .

Answer 2

Este es el principio del supermercado:

Considere $k+P-1$ objetos alineados en una línea. Elija $k$ de ellos como "divisores". Entonces hay una biyección entre los objetos y los divisores con el número de objetos en cada caja.