# How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ with restrictions

So i was Given this question. How many different integer solutions are there to the equation

$x_1 + x_2 + x_3 + x_4 = 21$

$0 \leq x_i \leq 9$?

I just assumed it would be

${21+4-4-1 \choose 4-1} = {20 \choose 3}$

I'm confused by the $0 \leq x_i \leq 9$.

• For the first part, if there was a first part, was it solutions in positive integers? Non-negative integers? If positive integers then your $\binom{20}{3}$ is right. But it is not the answer if the $x_i$ are restricted to $0$ to $9$. – André Nicolas Feb 9 '16 at 18:31
• Could you define 'different'? Are 9+9+3+0 and 9+9+0+3 different? – Octania Feb 9 '16 at 18:32
• @Octania that was the only thing given by the question – Zero Feb 9 '16 at 18:39
• By how it's written, I assume 9+9+3+0 and 9+9+0+3 are different (it makes a difference in the formulas to use) – Octania Feb 9 '16 at 18:45

## 3 Answers

This can be expressed as the coefficient of $x^{21}$ in the binomial expansion of $$(1+x+x^2+\cdots+x^9)^4$$

This is because the coefficient will represent the number of ways $4$ powers of $x$, ranging from $0$ to $9$, can add up to $21$. Thus you get the number of solutions to the given equation.

Each variable has been replaced with a series in $x$ whose terms contain in the powers all the allowed values of $x$. All these series' have been multiplied with each other. The logic behind this is that when two terms are multiplied, their powers add up. So, the coefficient of the sum you want gives the number of ways in which the power was achieved, which is the same as the number of ways the individual powers added up to the sum.

• can you explain how you got the binomial expansion and how this method works? – Zero Feb 9 '16 at 18:34
• @Zero You need to find the number of ways four numbers with the given restriction add up to $21$. Each variable has been replaced with a series in $x$ whose terms contain in the powers all the allowed values of $x$. All these series' have been multiplied with each other. The logic behind this is that when two terms are multiplied, their powers add up. So, the coefficient of the sum you want gives the number of ways in which the power was achieved, which is the same as the number of ways the individual powers added up to the sum. – GoodDeeds Feb 9 '16 at 18:48
• Does this take into account the restriction $0\leq x_i \leq9$? – Octania Feb 9 '16 at 19:03
• @Octania Yes, because the powers of $x$ range only from $0$ to $9$ – GoodDeeds Feb 9 '16 at 19:09

Let S be the set of all solutions in nonnegative integers, and

let $E_i$ be the set of solutions with $x_i\ge10$ for $1\le i\le4$.

Using Inclusion-Exclusion,

$\displaystyle|\overline{E_1}\cap\cdots\cap\overline{E_4}|=|S|-\sum_{i}|E_i|+\sum_{i<j}|E_i\cap E_j|-\sum_{i<j<k}|E_i\cap E_j\cap E_k|+|E_1\cap\cdots\cap E_4|$

$\hspace{1.0 in}\displaystyle=\binom{24}{3}-\binom{4}{1}\binom{14}{3}+\binom{4}{2}\binom{4}{3}=592$

### All solutions

Split $(x_{1}+x_{2})+(x_{3}+x_{4})=21$. There are 16 different pairs $(x_{1}+x_{2},x_{3}+x_{4})$ (if you count $3+18$ different from $18+3$) simply $(3,18),(4,17),(5,16),...,(10,11),...,(18,3)$

For $(10,11)$ and $(11,10)$ you have $9$ combinations for $10$ and $8$ combinations for $11$. That makes $2\cdot 9 \cdot 8=144$ combinations.

For $(9,12)$ and $(12,9)$ you have $10$ combinations for $9$ and $7$ combinations for $12$.

For $(8,13)$ and $(13,8)$ you have $9$ combinations for $8$ and $6$ combinations for $13$.

...

The pattern emerges $2m(m-3)$. So the total number of solutions is then

$$144+ \sum\limits_{m=4}^{10} 2m(m-3) = 592$$