Number of ways of adding k positive numbers to obtain a fixed number $M$

Question

This problem is close to a standard problem: the number of ways of adding up non-negative integers to form a given fixed number $M$.

However in this case there are two constraints: 1) each of the summands has to be strictly greater than 0, and 2) the total number of summands is fixed at length $k$.

• for $k=1$ the answer is easy, 1
• for $k=2$ the answer is 2(sum from 1 to floor(M/2)).

So obviously that's enough to create a recursive algorithm that would allow one to calculate the answer to the question for any specific values of M and k, but I'm wondering if there is any closed form solution for arbitrary $M$ and $k$?

Another way to express this is the number of partitions of a non-empty set of finite cardinality $M$ where the number of parts (or blocks) in each partition is a fixed value $k$.

Answer 1

It appears from your second example that the order of summation matters (1+2 and 2+1 are distinct). In that case, consider the summands as k bins that you have to fill with M objects. It is clearly a combinations-with-repetition problem. Remember to reduce M by k, denoting how you took care not to leave any bins empty.

Answer 2

This is precisely the stars and bars algorithm. You have $M$ stars and $M-1$ places to put bars between them. Each of your integers is the number of stars between neighboring bars. You need to place $k-1$ bars to get $k$ blocks of stars, so there are $$M-1 \choose k-1$$ ways to do it.