Cuántas maneras de elegir $X$ bolas

Question

Supongamos que tengo $3$ tipos de bolas $A,B$ y $C$ y hay $n_a, n_b,$ y $n_c$ copias de estas bolas. Ahora quiero seleccionar $x$ bolas de estos $3$ tipos de bolas $x < n_a + n_b + n_c$ . ¿Puede alguien ayudarme a llegar a la fórmula cerrada para esto.

Pensé, si yo partición $x$ en $3$ partición que va a hacer, pero en ese caso es muy posible que yo pueda recoger más bolas de determinado tipo que su recuento real.

Answer 1

Lo que se busca es el coeficiente de $k^x$ en $(1+k+k^2\dots k^{n_a})(1+k+k^2\dots k^{n_b})(1+k+k^2\dots k^{n_c})$

Answer 2

Como dice la respuesta de Bananarama, lo es: \begin{align} [z^n] (1 + z + \ldots + z^{n_a})& (1 + z + \ldots + z^{n_b}) (1 + z + \ldots + z^{n_c}) \\ &= [z^n] \frac{1 - z^{n_a + 1}}{1 - z} \cdot \frac{1 - z^{n_b + 1}}{1 - z} \cdot \frac{1 - z^{n_c + 1}}{1 - z} \\ &= [z^n] \frac{(1 - z^{n_a + 1}) (1 - z^{n_b + 1}) (1 - z^{n_c + 1})}{(1 - z)^3} \\ \end{align} Multiplique el denominador, entonces usted puede escoger los términos respectivos de $$ (1 - z)^{-3} = \sum_{k \ge 0} (-1)^k \binom{-3}{k} z^k = \sum_{k \ge 0} \binom{k + 3 - 1}{3 - 1} z^k $$ Por último, los coeficientes binomiales son polinomios cuadráticos en $k$ .

Answer 3

Este problema puede resolverse fácilmente con Principio de inclusión Exclusión (PIE) y el Bolas y urnas técnica. La respuesta es:

$\dbinom{x+2}{2} - \dbinom{x-n_a+1}{2} - \dbinom{x-n_b+1}{2} - \dbinom{x-n_c+1}{2} + \dbinom{x-n_a-n_b}{2} + \dbinom{x-n_a-n_c}{2} + \dbinom{x-n_b-n_c}{2} - \dbinom{x-n_a-n_b-n_c-1}{2}$ .

Pista: Cada término corresponde al número de soluciones enteras no negativas $(a,b,c)$ a $a+b+c = x$ con 0, 1, 2 o 3 de las siguientes condiciones aplicadas:

$a > n_a$

$b > n_b$

$c > n_c$

Answer 4

Tengo la misma pregunta y estoy buscando una solución que escale en gran medida y no me quedó claro cómo se cierran las otras respuestas aquí o cómo puedo implementarlas para problemas arbitrariamente grandes.

He aquí una no cerrado solución, sólo para documentar mi propio progreso en este problema:

---

Existen $\{b_1, b_2, \ldots, b_n\}$ copias de las bolas.

Estamos seleccionando $x$ pelotas.

La solución trivial:

$$f(x, \{b_1\})=\begin{cases}1,&x<=b_1\\0,&x>b_1\end{cases}$$

La parte recursiva:

$$f(x, \{b_1, b_2, \ldots, b_n\}) = \sum_{i=0}^{b_1}f(x-i,\{b_2, \ldots, b_n\})$$