Número de soluciones para$x[1] + x[2] + \ldots + x[n] =k$

Question

Omg, esto me está volviendo loco en serio, es un subproblema para un problema más grande, y estoy atrapado en él.

De todos modos, necesito el número de formas para seleccionar$x[1]$ cantidad de objetos tipo$1$,$x[2]$ cantidad de objetos tipo$2$,$x[3]$ cantidades de objetos tipo$3$ etc., etc., tal como$$x[1] + x[2] + \ldots x[n] = k\;.$ $ El orden de los objetos, por supuesto, no importa.

Sé que hay una fórmula simple para este algo como$\binom{k + n}n$ o algo así, simplemente no puedo encontrarlo en ninguna parte en google.

Answer 1

Este es un llamado problema de estrellas y barras ; el numero que quieres es

PS

El artículo vinculado tiene una explicación razonablemente buena del razonamiento detrás de la fórmula.

Answer 2

La fórmula es:

$$ {n+k-1 \choose k} $$

He aquí una prueba:

Crear un vector con $n$ queridos y $k$ ceros, en ningún orden en particular. Cada permutación de este vector es una solución para $x_1 + x_2 + x_3 + \cdots + x_k = n$. $x_1$ es igual al número de unos a la izquierda de la primera cero, $x_2$ es igual al número de entre la primera y la segunda ceros, $x_3$ es igual al número de entre la segunda y la tercera ceros, y así sucesivamente, con el $x_i$ correspondiente al número de antes de la $(i-1)^{th}$ $i^{th}$ ceros. Hay una correspondencia uno a uno entre esta permutación y $x_1 + x_2 + x_3 + \cdots + x_k = n$. Hay $\dfrac{(n+k-1)!}{n!(k-1)!}$ permutaciones de un vector, por lo que por lo tanto la ecuación de la siguiente manera.

Answer 3

$\tbinom{k+n}{n}$ está cerca...pero no es del todo correcto:

Para cualquier par de números naturales $n$$k$, el número de los distintos n-tuplas de enteros no negativos cuya suma es $k$ está dado por el coeficiente binomial:

$$\displaystyle\binom{n+k+1}{n - 1}= \binom{n + k - 1}{k},\quad \text{ where}\;\quad \binom{n+k-1}k\,=\,\frac{(n+k-1)\,!}{n\,!\,(k-1)\,!}\;$$

Su problema es una versión del clásico "estrellas y barras problema" en la combinatoria.

---

Ver Coeficiente Binomial para obtener más información sobre las muchas maneras en las que el coeficiente binomial puede ser utilizado cuando, por qué y cómo es apropiado para un problema como el tuyo y muchos otros!