¿Diferentes formas de mantener las bolas N en las cajas K?

Question

De cuántas maneras diferentes puedo mantener N bolas en K cajas, donde cada caja debe contener al menos 1 pelota, N >> K y el número total de bolas en las cajas debe ser N ? Por ejemplo: para el caso de 4 bolas y 2 cajas, hay tres combinaciones diferentes: (1,3), (3,1) y (2,2).

¿Podría ayudarme a resolver esto, por favor? Por favor, también hágame saber si hay algún nombre clásico para este problema.

Answer 1

En sus ejemplos, las cajas se distinguen pero las bolas no.

Pues bien, como cada caja tiene que contener al menos una bola, coloca una bola en cada caja, lo que te deja con $N-K$ bolas para distribuir. El problema se convierte ahora en el problema de contar de cuántas maneras se puede distribuir $N-K$ bolas indistinguibles en $K$ cajas distinguibles, sin restricciones.

Resulta que es más fácil entonces simplemente seleccionar las cajas que tendrán las bolas. Para sus ejemplos, habiendo distribuido una bola cada uno en las dos cajas, nos queda el problema de colocar dos bolas en dos cajas. La primera combinación corresponde a la selección de la caja número $2$ dos veces; la segunda para seleccionar el número de caja $1$ dos veces; y la tercera para seleccionar la caja $1$ una vez y caja $2$ una vez.

Así que quieres hacer $N-K$ selecciones de entre $K$ cajas; el orden no importa; las repeticiones están permitidas. Se trata de un problema de "combinaciones con repeticiones", también conocido como el "problema de estrellas y barras" . El número de formas de hacer $s$ selecciones de entre $r$ posibilidades distinguibles, donde el orden no importa y se permiten las repeticiones es $$\binom{r+s-1}{s} = \frac{(r+s-1)!}{s!(r-1)!}.$$ En su ejemplo, tenemos $r=K = 2$ y $s=N-K=2$ Así que $\binom{2+2-1}{2} = \binom{3}{2}=3$ formas distintas.

Enchufar $N-K$ para $s$ y $K$ para $r$ obtenemos $$\binom{K+N-K-1}{N-K} = \binom{N-1}{N-K} = \binom{N-1}{K-1}.$$

Answer 2

Dejemos que $x_1, x_2,\dots,x_k$ sea el número de bolas colocadas en la caja $1,2,\dots,k$ respectivamente. Entonces se pide el número de soluciones en enteros positivos de la ecuación $$x_1+x_2+\cdots+x_k=n$$ Hay muchas maneras de hacerlo. Puede denotar este número con $f(n,k)$ y establecer una recurrencia, podrías encontrar una biyección entre estas soluciones y un conjunto más familiar o podrías utilizar funciones generadoras. Obsérvese que $f(n,k)$ es el coeficiente de $t^n$ en la expresión $$(t+t^2+\cdots)^k=\frac{t^k}{(1-t)^k}=t^k\left(\sum_{m=0}^{\infty}\binom{m+k-1}{k-1}t^m\right)$$ Así que el número que buscas es $\binom{n-1}{k-1}$ .