problema restringido de estrellas y barras

Question

Quiero saber el número de soluciones de la siguiente ecuación, donde $r_k$ son enteros no negativos, y existe una restricción sobre $r_k$ tal que $r_1 \geq r_2 \geq \cdots \geq r_K$

$$\begin{equation} r_1+r_2+\cdots+r_K=N \end{equation}$$

Answer 1

Queremos el número de particiones de $N$ en como máximo $K$ partes. Dadas las partes, hay exactamente una forma de ordenarlas en orden no creciente.

El número de particiones de $n$ en exactamente $k$ partes (distintas de cero). Para empezar, consulte la respuesta de Sammy Black. Desgraciadamente no se conoce ninguna forma cerrada agradable.

El número de particiones de $N$ en un máximo de $K$ piezas es lo mismo que el número de particiones de $N+K$ en exactamente $K$ partes.

Porque si tenemos una partición de $N+K$ en exactamente $K$ partes, restando $1$ de cada parte obtenemos una partición de $N$ en un máximo de $K$ partes. Y si tenemos una partición de $N$ en un máximo de $K$ partes, añadiendo $1$ a cada parte obtenemos una partición de $N+K$ en $K$ partes.

Answer 2

EDITAR: Esta respuesta responde a una pregunta ligeramente diferente, en la que $K$ (el número de sumandos) puede variar. Lo dejaré aquí para la posteridad, pero no merece ningún upvotes.

---

Estos son los particiones de enteros de $N$ . No existe una fórmula cerrada para $p(N)$ el número de tales particiones, aunque existe una bonita función generadora: $$\begin{align} \sum_{N=1}^\infty p(N) x^N &= \prod_{k=1}^{\infty} \frac{1}{1-x^k} \\ &= (1 + x + x^2 + x^3 + \cdots) (1 + x^2 + x^4 + x^6 + \cdots) (1 + x^3 + x^6 + x^9 + \cdots) \cdots \end{align}$$ El comienzo de esta expansión es $$1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 + 11x^6 + \cdots$$ que es otra forma de decir que para $N = 0, 1, 2, 3, \dots$ los valores de $p(N)$ son $$1, 1, 2, 3, 5, 7, 11, \dots$$