0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – user545963 Apr 3 '18 at 19:04
  • $\begingroup$ I'm not quite sure of what you mean by "differences between consecutive ones". Could you please give me an example? Thanks. $\endgroup$ – AsmiK Apr 3 '18 at 19:08
  • $\begingroup$ Added the explanation. Essentially, it is transforming the new problem to a version of the old one. $\endgroup$ – user545963 Apr 3 '18 at 19:08
  • $\begingroup$ You are asking about the much-studied subject of partitions. You will find lots of information on that web page. $\endgroup$ – Rob Arthan Apr 3 '18 at 19:12
  • $\begingroup$ Ok, I see what you're saying noodlesGroup. Thanks for the link, Rob Arthan. $\endgroup$ – AsmiK Apr 3 '18 at 19:14
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.