How many non-negative integer solutions does $x_1+x_2+\cdots+x_n=A$ have?

Question

If I have the Diophantine equation $\displaystyle{\sum_{i=1}^n x_i =A}$, is there a function $f(n,A)$ that will yield the number of non-negative integer solutions of the equation?

Answer 1

The number of solutions ($x_i,A\in\Bbb Z_{\ge 0}$) to $\displaystyle{\sum_{i=1}^n x_i=A}$ is

$$\displaystyle{f(n,A)=\left[\left(\frac{1}{1-x}\right)^{n}\right]_{x^A}}=\left(\!\binom{n}{A} \!\right)=\binom{n+A-1}{A}$$

Here $\left(\!\binom{n}{A}\!\right)$ denotes multiset coefficient.

I.e. $f(n,A)$ is the coefficient of $x^A$ in the polynomial $$\left(1+x+x^2+\cdots+x^A\right)^n$$

Note we used the geometric series formula:$$|x|<1\implies 1+x+x^2+x^3+\cdots=\frac{1}{1-x}$$

E.g., $x_1+x_2+x_3+x_4=15$ has $\displaystyle{\binom{4+15-1}{15}}=816$ non-negative integer solutions $x_i$.

See this answer for how to find the coefficients of other generating functions. This is the method of using generating functions in combinatorics, and it can be used to solve recurrence relations too.

Answer 2

If you're looking to partition positive integer $A$ into non-negative $x_i$ where $\sum_{i=1}^{n}x_i = A$, then there are $\binom{A+n-1}{n-1}$ ways to partition it.

Consider the set of binary strings with $A$ '$1$' digits and $(n-1)$ '$0$' digits. Think of each '$0$' as being a boundary between partitions, and each (possibly empty) substring of '$1$'s being the content of an $x_i$.

$0111101101011$ would correspond to a partition of $A=9$ into $n=5$ partitions with $x_i = \{0,4,2,1,2\}$

Every binary string with $A$ '$1$' digits and $(n-1)$ '$0$' digits will be of length $A + n - 1$, and there are $\binom{A + n - 1}{n - 1}$ of them.