# How many integer solutions are there to $x_1+x_2+x_3+x_4+x_5 = 28$ with certain restraints?

How many integer solutions are there to $x_1+x_2+x_3+x_4+x_5 = 28$ with:
a) $x_i \ge 0$?
b) $x_i > 0$?
c) $x_i \ge i (i = 1, 2, 3, 4, 5)?$

I know how I would count these, for example, a) I would start with one integer being 28, the rest 0, its combinations, and then subtract and distribute, but how do I count when the numbers start getting smaller and the distributions are difficult to keep track of? Is there an easy method to do this?

• for part (c), you can let $y_i=x_i-i$, and the question will be reduced to previous parts. – user220124 Mar 12 '16 at 23:50
• Are you familiar with combinations with repetition? – N. F. Taussig Mar 12 '16 at 23:50
• Try replacing 28 with a smaller number, like 7, or 3, and doing part (b). If that still doesn't work, try replacing 5 with a smaller number, too. I guarantee you know the sorts of numbers showing up in the answers; the trick is to get some data! – Eric Stucky Mar 12 '16 at 23:52
• Use Stars and Bars – Foobaz John Mar 12 '16 at 23:53
• Yes its ${n+r-1 \choose r}$ but how would I incorporate that here? – Jodo1992 Mar 12 '16 at 23:53

## 2 Answers

How many solutions does the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 28$ have in the non-negative integers?

A particular solution to the equation in the non-negative integers corresponds to the placement of four addition signs in a row of $28$ ones. For instance, $$1 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 + + 1 1 1 1$$ corresponds to the solution $x_1 = 9$, $x_2 = 8$, $x_3 = 7$, $x_4 = 0$, and $x_5 = 4$. Thus, the number of solutions of the equation in the non-negative integers is the number of ways four addition signs can be placed in a row of $28$ ones, which is $$\binom{28 + 4}{4} = \binom{32}{4}$$ since we must choose which four of the $32$ symbols (four addition signs and $28$ ones) will be addition signs.

In general, the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the non-negative integers is equal to the number of ways $k - 1$ addition signs can be inserted into a row of $n$ ones, which is $$\binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n}$$ since we must choose which $k - 1$ of the $n + k - 1$ symbols ($n$ ones and $k - 1$ addition signs) will be addition signs or, alternatively, which $n$ of the symbols will be ones.

How many solutions does the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 28$ have in the positive integers?

A particular solution of the equation in the positive integers corresponds to the placement of four addition signs in the $27$ spaces between successive ones in a row of $28$ ones. For instance, $$1 1 1 1 1 1 + 1 1 1 1 1 1 1 + 1 1 1 1 1 1 + 1 1 1 1 1 + 1 1 1 1$$ corresponds to the solution $x_1 = 6$, $x_2 = 7$, $x_3 = 6$, $x_4 = 5$, and $x_5 = 4$. Thus, the number of solutions of the equation in the positive integers is the number of ways four addition signs can be placed in the $27$ gaps between successive ones in a row of $28$ ones, which is $$\binom{27}{4}$$ In general, the number of solutions of the equation $$x_1 + x_2 + \cdots + x_k = n$$ in the positive integers is the number of ways $k - 1$ addition signs can be placed in the $n - 1$ gaps between successive ones in a row of $n$ ones, which is $$\binom{n - 1}{k - 1}$$

How many solutions does the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 28$ have in the integers subject to the restraints $x_k \geq k$, $1 \leq k \leq 5$.

Hint: Let $y_k = x_k - k$, $1 \leq k \leq 5$. Substitute $y_k + k$ for $x_k$, $1 \leq k \leq 5$, then solve the resulting equation in the non-negative integers.

• What of part c)? – Jodo1992 Mar 13 '16 at 1:31
• If you follow my hint, you obtain \begin{align*} y_1 + 1 + y_2 + 2 + y_3 + 3 + y_4 + 4 + y_5 + 5 & = 28\\ y_1 + y_2 + y_3 + y_4 + y_5 & = 13\end{align*} Since $x_k \geq k$, $1 \leq k \leq 5$, $y_k = x_k - k \geq 0$ for $1 \leq k \leq 5$. Thus, we must solve the equation $y_1 + y_2 + y_3 + y_4 + y_5 = 13$ in the non-negative integers. Using the reasoning outlined in (a), the number of solutions is $$\binom{13 + 4}{4} = \binom{17}{4}$$ – N. F. Taussig Mar 13 '16 at 1:55

While the problem does not ask for such, a generating-function approach is particularly flexible.

First case: Each $x_k$ is some nonnegative integer. (Those larger than 28 will not be relevant, but it is simpler not to exclude these cases explicitly.) This is represented by the generating function (GF) $$g(t)=t^0+t^1+t^2+\cdots =\sum_{k=0}^\infty t^k = \frac{1}{1-t}$$ i.e. the geometric series. Integer combinations of $n$ such terms are then generated by $p(t)^n$, with the $k$-th coefficient $[t^k]p(t)^n$ counting how many such combinations add to $k$.

But these coefficients are known: The negative binomial series satisfies $$(1-t)^{-n-1}=\sum_{k=0}^\infty \binom{n+k}{n}t^k\hspace{.5cm}\implies \hspace{.5cm}[t^k](1-t)^{-n-1}=\binom{n+k}{n}$$ and so we can count such combinations explicitly. In particular, we have $[t^{28}]{(1-t)^{-5}}=\binom{32}{4}$ as the answer for part $(a)$ of the question (the same as found in N.F. Taussig's answer).

Second case: We now further require that $x_k>0$. But this only changes the initial GF to $t p(t)=t^1+t^2+t^3+\cdots = t(1-t)^{-1}$. Consequently the relevant coefficient is now $[t^k]t^n p(x)^n=[t^{k-n}]p(x)^n$, and for the case $(n,k)=(5,28)$ we obtain $[t^{23}](1-t)^{-5}=\binom{27}{4}$ (once more in agreement with Taussig's answer) as the number of positive integer combinations.

Third case: Now the $x_k$ have distinct constraints $x_k\geq k$. Hence each has a different GF. But as in the second case, all that changes is that each GF picks up a prefactor i.e. $p_k(t)=t^k p(t)=t^k(1-t)^{-1}$. Hence the GF for integer combinations in the case at hand is $$p_1(t)p_2(t)p_3(t)p_4(t)p_5(t)=\frac{t^1}{1-t}\frac{t^2}{1-t}\frac{t^3}{1-t}\frac{t^4}{1-t}\frac{t^5}{1-t}=\frac{t^{15}}{(1-t)^5}.$$ From this we obtain the number of constrained integer combinations for the case $k=28$ as $$[t^{28}]\frac{t^{15}}{(1-t)^{5}}=[t^{13}]\frac{1}{(1-t)^{5}}=\binom{17}{4}$$ which is in agreement with the result reported in a comment of Taussig's answer.

As a postscript, this method gives us an immediate corollary: The number of integer combinations of $n$ in $k$ terms with constraints $\{x_k\geq a_k\}$ depends only on $\sum_k a_k$.