I am aware the number of distinct non-negative integer-valued vectors $(x_1, x_2, ..., x_r)$ satisfying the equation $x_1 + x_2 + ... + x_r = n$ is given by

$$n+r-1 \choose r-1$$

However, is there a formula to compute the number of distinct combinations of non-negative integers $ \{x_1, x_2, ..., x_r\}$ that satisfy the equation $x_1 + x_2 + ... + x_r = n$?

In other words, for $n=r=2$, the former formula will return

$${2+2-1 \choose 2-1}={3 \choose 1}=3$$

conveying there are $3$ distinct non-negative integer-valued vectors that satisfy $x_1+x_2=2$, that is, $(1,1),(2,0)$ and $(0,2)$. However, I am seeking a formula that will convey there are $2$ distinct combinations of non-negative integers that satisfy $x_1+x_2=2$, that is, $\{1,1\}$ and $\{2,0\}$.

Does such a formula exist?

Thank you!

  • 1
    $\begingroup$ Do you know how this formula comes about? The key lies in the derivation $\endgroup$ – Dhanvi Sreenivasan May 1 '20 at 6:15
  • $\begingroup$ Yes, I am aware how it is derived. but i still cannot seem to grasp it $\endgroup$ – RyRy the Fly Guy May 1 '20 at 6:16
  • $\begingroup$ @RyRytheFlyGuy You mean order should not matter? $\endgroup$ – jPratik May 1 '20 at 6:21
  • 4
    $\begingroup$ Oh, I'm sorry, my comment was unfounded. This is a much tougher problem. en.wikipedia.org/wiki/Partition_%28number_theory%29 $\endgroup$ – Dhanvi Sreenivasan May 1 '20 at 6:27
  • 1
    $\begingroup$ @DhanviSreenivasan Thank you. It is encouraging to know I am stumped over a true mystery and not something simple. $\endgroup$ – RyRy the Fly Guy May 1 '20 at 6:33

The number of partitions of a number $ n $ into $k $ non-negative parts, $P (n,k) $ can be readily computed using the following recurrence relation: $$P(n,k)=\begin {cases} 0,& n<0\text{ or } k<0\\ 1,&n=0,k=0\\ P(n,k-1)+P(n-k,k),&\text{otherwise}. \end {cases}\tag1 $$

The proof of the recurrence relation (1) can be carried out as follows. The partitions of the number $n$ into $k$ non-negative parts can be subdivided in those which have at least one summand equal to $0$ and those which have only positive summands. In the latter case we can subtract $1$ from every summand to obtain a partition of $n-k$ into $k$ parts. In the former case we can consider $0$ as a given part and reduce the problem to partitioning of the number $n$ into $k-1$ parts.


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.