I'm working on an assignment in which I have to count the number of solutions for this particular equation: $$x_1+x_2+x_3+x_4=20$$for non negative integers with $x_1<8 $ and $x_2<6$
I'm aware that this kind of a task isn't that complicated, but I don't get combinatorics in general that well.
So I've tried two following approaches to get this done.
Firstly I tried to substitute the variable x:
$x_1+x_2+x_3+x_4=20 \Leftrightarrow y_1+y_2+y_3+y_4=34$
in which $y_1=x_1+8$ and $y_2=x_2+6$ (casue $x_1=y_1-8$ and $x_2=y_1-6$)
Following this approach the total number of possible solutions would be
$${34+3 \choose 3} $$
But I'm not sure if its the right solution.
The second approach is to sum all of the possible values that $x_1$ and $x_2$ could possibly take, also $x_1=0,1,2,3,4,5,6,7$ and $x_2=0,1,2,3,4,5,6$
And then count all the possibilities for each of the variables $${20 -x_1-x_2+1\choose 1}$$
and sum them together like this:
$${21\choose 1}+{20\choose 1}+{19\choose 1}+{18\choose 1}+… $$
and so on…
I'm sure I'll get the correct number with this one, but I'm not feeling like summing all of this possibilities. There's got to be a better, more elegant way to deal with this.
My professor gave me a hint that I should do it using the complement.
Best Answer
One way of looking at it is this: The number of ways is just the coefficient of $x^{20}$ in the expansion of $$(1+x+x^2+\cdots+x^7)(1+x+x^2+\cdots+x^5)(1+x+x^2+\cdots+x^{20})^{2}$$
Here, each factor represents a term in your equation (here I have written them in the same order). The powers of $x$ in the factor are the values the corresponding variable can take. I limited the last two factors to a maximum power of $20$ as all the terms are non negative.
Now, the logic behind this is that when you multiply two powers of $x$, the powers add up. The coefficient of $x^{20}$ gives the number of ways you could have multiplied various powers from each factor to get a total power of $20$. Notice that each combination of powers from each factor contributes to an increase of one in the coefficient and also represents a unique solution to your equation. Thus, the coefficient of $x^{20}$ in the binomial expansion gives the desired answer.
Each factor can be simplified by using the formulae for the sum of terms in a geometric progression. Then, the $(1-x)^{-n}$ terms can be expanded using the binomial expansion, after which the coefficient can be found easily.
$$(1+x+x^2+\cdots+x^7)(1+x+x^2+\cdots+x^5)(1+x+x^2+\cdots+x^{20})^{2}=\frac{(1-x^8)(1-x^6)(1-x^{21})^2}{(1-x)^4}$$
So, you need to find the coefficient of $x^{20}$ in the expansion of $$(1-x^8)(1-x^6)(1-x)^{-4}$$ The $(1-x^{21})^2$ term can be ignored, as terms with coefficient higher than $20$ are not of any concern. $$(1-x^8)(1-x^6)(1-x)^{-4}=(1-x^6-x^8+x^{14})(1+4x+10x^2+20x^3+\cdots+84x^{6}+\cdots+455x^{12}+\cdots+680x^{14}+\cdots+1771x^{20}+\cdots+\binom{n+3}{n}x^n+\cdots)$$ The coefficient is thus: $$1771-455-680+84=720$$