number of combinations of integers that satisfy equation

Question

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!

Answer 1

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.