How many possibilities are there of writing a natural number $M$ as a sum of $N$ natural numbers between $0$ and $M$?

For example, I need to write $4$, using $4$ numbers between $0$ and $4$. The possibilities are $$\begin{eqnarray*} 0+0+1+3 = 4 \\ 0+0+0+4 = 4 \\ 1+1+1+1 = 4 . \end{eqnarray*}$$

  • $\begingroup$ So you want to count the number of partitions of $8$ into $4$ (non-zero) parts, or in general of $2M$ into $M$ parts. $\endgroup$ – André Nicolas Jun 9 '15 at 19:13
  • $\begingroup$ See en.wikipedia.org/wiki/…. There is no closed-form formula, but you can calculate the number of partitions using recurrence relations or generating functions. $\endgroup$ – user7530 Jun 9 '15 at 19:15
  • $\begingroup$ The formula should be ${M+N \choose N}$, I believe. $\endgroup$ – abnry Jun 9 '15 at 19:16
  • 1
    $\begingroup$ The range of responses in Comments reflects the uncertainty whether the order of summands is considered in counting. Your examples suggest the order doesn't matter, but it would be better to state this explicitly. In that case you are asking about partitions of $M$ with at most $N$ parts. $\endgroup$ – hardmath Jun 9 '15 at 19:23
  • $\begingroup$ Please see the problem : [link] codechef.com/JUNE15/problems/STDYTAB $\endgroup$ – Habib Rahman Jun 9 '15 at 19:36

The answer is \begin{equation} p\left(M,N\right)=\binom{M+N-1}{N-1}=\frac{\left( M+N-1\right)\;!}{M\;!\left( N-1\right)\;!} \tag{1} \end{equation} but concerns ordered solutions $\left(x_{1},x_{2},\cdots ,x_{N}\right)$ : \begin{equation} x_{1}+x_{2}+\cdots +x_{N}=M \tag{2} \end{equation} So for $M=4$ and $N=4$ \begin{equation} p\left(4,4\right)=\binom{4+4-1}{4-1}=\frac{7\;!}{4\;!3\;!}=\frac{7\cdot 6 \cdot 5}{3 \cdot 2}=35 \tag{3} \end{equation}

The solutions $\left(0,1,3,0\right)$ and $\left(1,0,3,0\right)$ are considered different although they have the same summands.


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.