How many distinct combinations of N natural numbers sum to a given natural number W?
For example; for $W=16, N=4$ two of the combinations are $(4,4,4,4)$ and $(5,4,4,3)$
Note: Combination not permutation. $(5,4,4,3)$ and $(5,4,3,4)$ are equivalent.
Note: Excludes $0$.
I'd like to know;
- Some way to calculate how many combinations there are.
- Some process to iterate over each combination.
You are asking about the number of partitions of $W$ into $N$ parts. They define $p_k(n)$ as the number of partitions of $n$ into exactly $k$ parts and show that it is the same as the number of partitions of $n$ with largest part exactly $k$. This then gives the recurrence $p_k(n)=p_k(n-k)+p_{k-1}(n-1)$ The first term counts the partitions that have two or more occurrences of $k$, so if you remove one the largest is still $k$. The second term counts the partitions that have a single occurrence of $k$, so if you remove one item from that partition, you are now making a partition of $n-1$ objects with largest part $k-1$
Added in response to comment: Yes,if $k \gt n$ there are no partitions of $n$ with a part of $k$. For iterating over them, I would start with the largest possible part and go down. The largest part can be at most $W-N+1$, in which case all the rest must be $1$'s. The largest part must be at least $\lceil \frac WN \rceil$.I would write a routine list(W,N) that loops over the largest parts, calling list(W-largest part,N-1) and prefacing each list with the largest part.