Find the number of solutions of $a_0+a_1+a_2=17$ if $2\le a_0\le 5$, $3\le a_1\le 6$, $4\le a_2\le 7$.
This is an exmaple given by my professor, and his solution is:
The number of solutions to this equation satisfying the given constraints is equal to the coefficient of $x^{21}$ in the expression $$\left(\sum_{n=2}^5x^n\right)\left(\sum_{n=3}^6x^n\right)\left(\sum_{n=4}^7x^n\right)=x^9\left(\sum_{n=0}^3x^n\right)\left(\sum_{n=0}^3x^n\right)\left(\sum_{n=0}^3x^n\right).$$ This must be 3, since the coefficient of $x^8$ in $(1+x+x^2+x^3)^3$ is 3.
I understand actually nothing here. The expression of summation just pops up, and then comes the answer. What I only know that the idea of generating function is used here.
Can someone help explain how the steps in the solution come?
generating function.
This is another method that you may be interested.
$2\le a_0\le 5$, $3\le a_1\le 6$, $4\le a_2\le 7$.
$0\le a_0-2\le 5-2$, $0\le a_1-3\le 6-3$, $0\le a_2-4\le 7-4$.
$0\le b_0\le 3$, $0\le b_1\le 3$, $0\le b_2\le 3$.
$ a_0-2 = b_0, a_1-3 = b_1, a_2-4 = b_1$
$ a_0 =b_0+2, a_1 = b_1+3, a_2 = b_2+4$
$b_0+b_1+b_2+2+3+4 = 17$
$b_0+b_1+b_2 = 17-9 = 8$
Now $y_0 = 3-b_0, y_1 = 3-b_1, y_2= b_2 = 3-b_2, y_i's \gt 0$
$9-y_0+y_1+y_2 = 8$
$ y_0+y_1+y_2 = 1$
The number of solutions $= {(1+3-1)\choose(3-1)} = {3\choose2} = 3$
What I have given you is another solution using stars and bars.
$(x^2+x^3+x^4+x^5)(x^3+x^4+x^5+x^6)(x^4+x^5+x^6+x^7)$ is what your professor has shortened with summation signs.
How did you get this, the first expresssion in the bracket corresponds to values that $a_0$ can take. The way it is represented in generating function is $a_0=0$ is 1, $a_0=1$ is $x$, $a_0=2$ is $x^2$ and so on. $a_0$ can take values of {2,3,4,5} hence the first four terms of $x$ in the first bracket. Next a_1=3 is $x^3$, $a_1=4$ is $x^4$. $a_1=5$, is $x^5$ and $a_1=6$ is $x^6$. and hence the first four terms of x in the second bracket and now you can figure out how the thrid bracket of x terms are derived.
Now take $x^2$, $x^3$ and $x^4$ from all three bracketed expresssions what you then have is
$$x^2(1+x+x^2+x^3)\cdot x^3(1+x+x^2+x^3)\cdot x^4(1+x+x^2+x^3)=x^9(1+x+x^2+x^3)^3$$
What you are looking for is the coefficient of $x^{17}$, since we already took out $x^9$, we are looking for the coefficient of $x^8$ which is second term of the expansion of the expression in the brackets. if you expand $(1+x+x^2+x^3)^3$ using the binomial theorem, the equation becomes
$$(1+x+x^2+x^3)^3=\sum_{n=0}^3\binom{n}{3}1^n(x+x^2+x^3)^{3-n}$$
There can't be $x^8$ in $(x+x^2+x^3)^0$, $(x+x^2+x^3)$, and $(x+x^2+x^3)^2$, so $x^8$ appears only in $(x+x^2+x^3)^3$. Note that
$$(x+x^2+x^3)^3=(x+x^2+x^3)^2\cdot (x+x^2+x^3)=(x^6+2x^5+\dots)(x+x^2+x^3)$$
Hence, we obtain that the coefficient of $x^8$ is 3.