# number of combinations of integers that satisfy equation

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!

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