# Number of ways to write a number $N$ as the sum of $M$ natural numbers, where order doesn't matter?

Is there a formula to write a number $N$ as the sum of $M$ natural numbers (not necessarily distinct), where order DOES NOT matter? I know that you can use ${N-1}\choose{M-1}$ to find the number of ways counting order, but I'm looking for a formula that defines, for example, $1+1+2$ and $1+2+1$ as the same.

1. How many ways are there to write 13 as the sum of 4 natural numbers if order does not matter?

2. How many ways are there to write 8 as the sum of 4 natural numbers if order does not matter?

3. How many ways are there to write 11 as the sum of 5 natural numbers if order does not matter?

Thanks!

• You can model this by ordering the numbers and then looking at the differences between consecutive ones. You are looking to count the number of solutions of $x_1+x_2+...+x_M=N$ such that $0\leq x_1\leq x_2\leq...\leq x_M$. Define $y_1=x_1$, $y_2=x_2-x_1$, $y_3=x_3-x_2$,...,$y_{M}=x_M-x_{M-1}$. Then, you want to count the number of solutions of $y_1+...+y_M=X_m\leq N$, with $y_i\geq0$. – user545963 Apr 3 '18 at 19:04
• I'm not quite sure of what you mean by "differences between consecutive ones". Could you please give me an example? Thanks. – AsmiK Apr 3 '18 at 19:08
• Added the explanation. Essentially, it is transforming the new problem to a version of the old one. – user545963 Apr 3 '18 at 19:08
• You are asking about the much-studied subject of partitions. You will find lots of information on that web page. – Rob Arthan Apr 3 '18 at 19:12
• Ok, I see what you're saying noodlesGroup. Thanks for the link, Rob Arthan. – AsmiK Apr 3 '18 at 19:14

This is a question about partitions. One is asking how many partitions of $N$ are there into exactly $M$ parts. Call this $P(N,M)$ One answer is that there is a generating function $$\sum_{N=M}^\infty P(N,M)x^N=\frac{x^M}{(1-x)(1-x^2)\cdots(1-x^M)}$$ for each $M$.