For a range of positive integers $1 - S$, how many collections of $N$ integers are there that their sum is a constant $S$.
Example:
- Integers from $1$ to $100$
- Collections of $4$ integers
- Each collection should sum to $100$
eg collections in this case are [22, 23, 34, 21] and [19, 7, 31, 43].
How many different collections can there be?
As developer, I am implementing in code different algorithms to produce these collections and would like to know when an algorithm has found eg. 20% of them.
I am interested in an explanation of how this number can be achieved for a given range and sum.
The value you are looking vor is named partition function $P(n,k)$. It can be computed by recurrence relation $$P(n,k)=P(n-k,k)+P(n-1,k-1), $$ with $P(n,k)=0$ for $n<k$, $P(n,0)=0$, and $P(n,n)=1$.
In particular, $P(100,4)=7153.$