Encuentra todos los conjuntos de N sumandos iguales a un total dado W

Question

¿Cuántas combinaciones distintas de N números naturales suman un número natural dado W?

Por ejemplo, para $W=16, N=4$ dos de las combinaciones son $(4,4,4,4)$ y $(5,4,4,3)$

Nota: Combinación, no permutación. $(5,4,4,3)$ y $(5,4,3,4)$ son equivalentes.
Nota: No incluye $0$ .

Me gustaría saberlo;

1. Alguna forma de calcular cuántas combinaciones hay.
2. Algún proceso para iterar sobre cada combinación.

Answer 1

Usted pregunta por el número de particiones de $W$ en $N$ partes. Definen $p_k(n)$ como el número de particiones de $n$ en exactamente $k$ partes y demostrar que es el mismo que el número de particiones de $n$ con la parte más grande exactamente $k$ . Esto da entonces la recurrencia $p_k(n)=p_k(n-k)+p_{k-1}(n-1)$ El primer término cuenta las particiones que tienen dos o más ocurrencias de $k$ Así que si se quita uno, el más grande sigue siendo $k$ . El segundo término cuenta las particiones que tienen una sola ocurrencia de $k$ por lo que si se elimina un elemento de esa partición, ahora se está haciendo una partición de $n-1$ objetos con la mayor parte $k-1$

Añadido en respuesta al comentario: Sí, si $k \gt n$ no hay particiones de $n$ con una parte de $k$ . Para iterar sobre ellas, yo empezaría por la parte más grande posible e iría bajando. La parte más grande puede ser como máximo $W-N+1$ en cuyo caso todo el resto debe ser $1$ 's. La parte más grande debe ser al menos $\lceil \frac WN \rceil$ .escribiría una rutina list(W,N) que hiciera un bucle sobre las partes más grandes, llamando a list(W-parte más grande,N-1) y precediendo cada lista con la parte más grande.