I have a question
Find the coefficient of $x^{10}$ in the expansion $(1+x+x^2+x^3+.....+x^{10})^4$
There ARE questions like this on stack exchange already I know, but I'm not able to formulate a pattern or know how to apply that thing here... I've tried making combinations of $1$'s and $x^{10}$'s, $x$'s and $x^9$'s etc but I am unable to solve it. Please help.
PS. How to do it using combinations exclusively.
On
So we have $$\left(\sum_{i=0}^{10}{x^i}\right)^4=\sum_{l=0}^{10}\sum_{k=0}^{10}\sum_{j=0}^{10}\sum_{i=0}^{10}{x^i x^j x^k x^l}.$$
We want all terms $x^i x^j x^k x^l$ such that $i+j+k+l=10.$ This implies that we simply need the number of partitions of $10,$ times $4!.$ Can you continue from here?
On
Try: $\begin{align*} 1 + x + &x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10} \\ &= \frac{1 - x^{11}}{1- x} \\ (1 + x + &x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10})^4 \\ &= \frac{(1 - x^{11})^4}{(1- x)^4} \\ &= (1 - 4 x^{11} + 6 x^{22} - 4 x^{33} + x^{44}) \cdot \sum_{k \ge 0} (-1)^k \binom{-4}{k} x^k \\ [x^{10}] (1 - &4 x^{11} + 6 x^{22} - 4 x^{33} + x^{44}) \cdot \sum_{k \ge 0} (-1)^k \binom{-4}{k} x^k \\ &= [x^{10}] \sum_{k \ge 0} (-1)^k \binom{-4}{k} x^k \\ &= (-1)^{10} \binom{-4}{10} \\ &= \binom{10 + 4 - 1}{4 - 1} \\ &= 286 \end{align*}$
On
Here is an approach using hardcore calculations
split $(1+x+x^2+\cdots +x^{10})^4$ like:
$(1+x+x^2+\cdots +x^{10})^4 = (1+x+x^2+\cdots +x^{10})^2 \cdot (1+x+x^2+\cdots +x^{10})^2$
and then calculate $(1+x+x^2+\cdots +x^{10})^2$ like:
$(\underbrace{1+x+x^2+\cdots +x^{10}}_{11 \text{ summands }})^2 = (1+x+x^2+\cdots +x^{10}) \cdot \color{red}{(1+x+x^2+\cdots +x^{10})}$
Multiply the terms together like:
$ 1 \cdot \color{red}{(1+x+x^2+\cdots +x^{10})} + x \cdot \color{red}{(1+x+x^2+\cdots +x^{10})} + x^2 \cdot \color{red}{(1+x+x^2+\cdots +x^{10})} + \cdots + x^{10} \cdot \color{red}{(1+x+x^2+\cdots +x^{10})}$
to get this:
$ \underbrace{(1+x+x^2+\cdots +x^{10}) + (x+x^2+x^3+\cdots +x^{11}) + \cdots + (x^{10}+x^{11}+x^{12}+\cdots +x^{20})}_{11 \times 11 \text{ summands }} $
Evaluate the above expression $s$ with $11 \times 11$ summands to get the following:
$s = 1+2x+3x^2+4x^3+5x^4+6x^5+7x^6+8x^7+9x^8+10x^9+11x^{10}+10x^{11}+9x^{12}+8x^{13}+7x^{14}+6x^{15}+5x^{16}+4x^{17}+3x^{18}+2x^{19}+x^{20} $
So, in $(1+x+x^2+\cdots +x^{10})^2 $ we can, just be looking at $s$, count $x^{10}$ exactly $11$ times. Now calculate $S = s^2 = (1+x+x^2+\cdots +x^{10})^4 $ like:
$$ S=(1+x+x^2+\cdots +x^{10})s+(x+x^2+x^3+\cdots +x^{11})s+ \cdots + (x^{10}+x^{11}+x^{12}+ \cdots +x^{20})s $$
The first term $(1+x+x^2+\cdots +x^{10})s$ of $S$ evaluates as:
$ \color{black}{1+2x+3x^2+4x^3+5x^4+6x^5+7x^6+8x^7+9x^8+10x^9+11x^{10}+10x^{11}+9x^{12}+8x^{13}+7x^{14}+6x^{15}+5x^{16}+4x^{17}+3x^{18}+2x^{19}+x^{20}}\color{red}{+x+2x^2+ 3x^3+4x^4+5x^5+6x^6+7x^7+8x^8+9x^9+10x^{10}+11x^{11}+10x^{12}+9x^{13}+8x^{14}+7x^{15}+6x^{16}+5x^{17}+4x^{18}+3x^{19}+2x^{20}+x^{21}}\color{blue}{+x^2+2x^3+ 3x^4+4x^5+5x^6+6x^7+7x^8+8x^9+9x^{10}+10x^{11}+11x^{12}+10x^{13}+9x^{14}+8x^{15}+7x^{16}+6x^{17}+5x^{18}+4x^{19}+3x^{20}+2x^{21}+x^{22}} \color{orange}{+ \cdots \cdots \cdots} \color{brown}{+x^{10}+2x^{11}+ 3x^{12}+4x^{13}+5x^{14}+6x^{15}+7x^{16}+8x^{17}+9x^{18}+10x^{19}+11x^{20}+10x^{21}+9x^{22}+8x^{23}+7x^{24}+6x^{25}+5x^{26}+4x^{27}+3x^{28}+2x^{29}+x^{30}} $
In this first term $(1+x+x^2+\cdots +x^{10})s$ of $S$ you can count $x^{10}$ exactly $11+10+9+\cdots+1$ times.
In an analogous manner:
In the second term $(x+x^2+x^3+\cdots +x^{11})s$ of $S$ you can count $x^{10}$ exactly $10+9+8+\cdots+1$ times.
In the third term $(x^2+x^3+x^4+\cdots +x^{12})s$ of $S$ you can count $x^{10}$ exactly $9+8+7+\cdots+1$ times.
...
In the last term $(x^{10}+x^{11}+x^{12}+ \cdots +x^{20})s$ of $S$ you can count $x^{10}$ exactly once.
Then add up the number $n$ of times $x^{10}$ pops up in $S$:
$n = (11+10+\cdots+1)+(10+9+\cdots+1)+(9+8+\cdots+1)+\cdots + 1 = 286$
And here is an approach using thinking in possibilities and combinations without much calculations
Because in $(1+x+x^2+\cdots+x^{10})^4$ we have to multiply each summand of $(x^0+x+x^2+\cdots+x^{10})$ with every summand in $(x^0+x+x^2+\cdots+x^{10})$ and repeat $4$ times, the question reduces to find out in how many different ways we get $x^{10}$ when calculating $x^ax^bx^cx^d=x^{a+b+c+d}$ and $0\leq a,b,c,d \leq 10$ (which means that each of $a,b,c$ and $d$ can take a value between $0$ and $10$)? This question reduces further to the number of ways we can add up $4$ numbers $0\leq a,b,c,d \leq 10$ to get $10$.
How many combinations of $0\leq a,b,c,d \leq 10$ are there, such that $a+b+c+d=10$? (Down below is the General answer)
Force $a$ to equal $0$ and calculate the number of possibilities for $b,c$ and $d$ that satisfy $b+c+d=10$. Then force $a$ to equal $1$ and calculate the number of possibilities for $b,c$ and $d$ that satisfy $b+c+d=9$. Then force $a$ to equal $2$ and calculate the number of possibilities for $b,c$ and $d$ that satisfy $b+c+d=8$... At last force $a$ to equal $10$ and calculate the number of possibilities for $b,c$ and $d$ that satisfy $b+c+d=0$.
Forcing $a$ to equal $0$ and calculation of the number of the possibilities for $b,c$ and $d$ that satisfy $b+c+d=10$ can be reduced to 11 steps:
1.Step: Forcing $a=0$ and $b=0$ and calculating the number of possibilities for $c,d$ that satisfy $c+d=10$. There exists exactly $11$ possibilities for $c,d$ that satisfy $c+d=10$, the first eleven possibilities can be given as:
No. $1: (a,b,c,d) = (0,0,0,10)$
No. $2: (a,b,c,d) = (0,0,1,9)$
No. $3: (a,b,c,d) = (0,0,2,8)$
No. $4: (a,b,c,d) = (0,0,3,7)$
No. $5: (a,b,c,d) = (0,0,4,6)$
No. $6: (a,b,c,d) = (0,0,5,5)$
No. $7: (a,b,c,d) = (0,0,6,4)$
No. $8: (a,b,c,d) = (0,0,7,3)$
No. $9: (a,b,c,d) = (0,0,8,2)$
No. $10: (a,b,c,d) = (0,0,9,1)$
No. $11: (a,b,c,d) = (0,0,10,0)$
Then we can generate another $10$ possibilities with forcing $a=0$, $b=1$ and $c+d=9$ like this:
2.Step: Forcing $a=0$ and $b=1$ and calculating the number of possibilities for $c,d$ that satisfy $c+d=9$. There exists exactly $10$ possibilities for $c,d$ that satisfy $c+d=9$, the second ten possibilities can be given as:
No. $1: (a,b,c,d) = (0,1,0,9)$
No. $2: (a,b,c,d) = (0,1,1,8)$
No. $3: (a,b,c,d) = (0,1,2,7)$
No. $4: (a,b,c,d) = (0,1,3,6)$
No. $5: (a,b,c,d) = (0,1,4,5)$
No. $6: (a,b,c,d) = (0,1,5,4)$
No. $7: (a,b,c,d) = (0,1,6,3)$
No. $8: (a,b,c,d) = (0,1,7,2)$
No. $9: (a,b,c,d) = (0,1,8,1)$
No. $10: (a,b,c,d) = (0,1,9,0)$
3.Step: Then we can generate another $9$ possibilities with forcing $a=0$, $b=2$ and $c+d=8$ like this:
No. $1: (a,b,c,d) = (0,2,0,8)$
No. $2: (a,b,c,d) = (0,2,1,7)$
No. $3: (a,b,c,d) = (0,2,2,6)$
No. $4: (a,b,c,d) = (0,2,3,5)$
No. $5: (a,b,c,d) = (0,2,4,4)$
No. $6: (a,b,c,d) = (0,2,5,3)$
No. $7: (a,b,c,d) = (0,2,6,2)$
No. $8: (a,b,c,d) = (0,2,7,1)$
No. $9: (a,b,c,d) = (0,2,8,0)$
and so on until step no. $11$. By the time we get to step no. $11$ we have got $11+9+8+7+6+5+4+3+2+1$ different possibilities from forcing $a$ to equal $0$ and varrying $b,c$ and $d$ such that $a+b+c+d=0+b+c+d=b+c+d=10$.
Now force $a$ to equal $1$ and calculate the number of possibilities for $b,c$ and $d$ that satisfy $b+c+d=9$.
1.Step:
No. $1: (a,b,c,d) = (1,0,0,9)$
No. $2: (a,b,c,d) = (1,0,1,8)$
No. $3: (a,b,c,d) = (1,0,2,7)$
No. $4: (a,b,c,d) = (1,0,3,6)$
No. $5: (a,b,c,d) = (1,0,4,5)$
No. $6: (a,b,c,d) = (1,0,5,4)$
No. $7: (a,b,c,d) = (1,0,6,3)$
No. $8: (a,b,c,d) = (1,0,7,2)$
No. $9: (a,b,c,d) = (1,0,8,1)$
No. $10: (a,b,c,d) = (1,0,9,0)$
2.Step:
No. $1: (a,b,c,d) = (1,1,0,8)$
No. $2: (a,b,c,d) = (1,1,1,7)$
No. $3: (a,b,c,d) = (1,1,2,6)$
No. $4: (a,b,c,d) = (1,1,3,5)$
No. $5: (a,b,c,d) = (1,1,4,4)$
No. $6: (a,b,c,d) = (1,1,5,3)$
No. $7: (a,b,c,d) = (1,1,6,2)$
No. $8: (a,b,c,d) = (1,1,7,1)$
No. $9: (a,b,c,d) = (1,1,8,0)$
and so on, at step no. $10$ we can count in total $10+9+8+7+6+5+4+3+2+1$ possibilities for the case that $a=1$ and $b+c+d=9$.
Now force $a=2$ and calculate the possible number of solutions for $b,c,d$ to satisfy $b+c+d=8$. We get $9+8+7+6+5+4+3+2+1$ possible combinations.
Now force $a=3$ and calculate the possible number of solutions for $b,c,d$ to satisfy $b+c+d=7$. We get $8+7+6+5+4+3+2+1$ possible combinations.
...
In total:
There number $n$ of different ways to add up four numbers between $0$ and $10$ ($0\leq a,b,c,d \leq 10$) to get a $10$ ($a+b+c+d=10$) is
$n = (11+10+\cdots+1)+(10+9+\cdots+1)+(9+8+\cdots+1)+\cdots + 1 = 286$
The second approach using combinations is better, because it can also be applied to more difficult questions.
This is a special solution of the following general statement: Let $k,N$ be natural numbers, then:
$$\binom{N+k-1}{k-1}$$
is the number of solutions for the equation:
$$x_1 + x_2 + \cdots +x_{k-1} + x_k = N$$
(German Paper about the number of partitions of a natural number $N$)
In our case we are looking for $4$ numbers, that add up to $10$:
$$x_1+x_2+x_3+x_4=10$$
That's why:
$$\binom{N+k-1}{k-1}=\binom{10+4-1}{4-1}=\frac{13!}{3! \cdot 10!} = \frac{13\cdot 12\cdot 11}{6} = 13 \cdot 11 \cdot 2 = 143 \cdot 2 = 286$$
On
The standard geometric series tells us that
$$1 +x + x^2 + x^3 + \ldots +x^{10}= \frac{1-x^{11}}{1-x}$$
So taking this to the fourth power we get
$$\left( \frac{1-x^{11}}{1-x} \right)^4 = (1-x^{11})^4 (1-x)^{-4}\tag{1}$$
This would not seem to really help much, except that for negative powers of $n$ there is a generalised binomial formula:
$$(1-x)^{-4} = \sum_{k=0}^\infty \binom{k+3}{k}x^k$$
The standard binomial formula gives us for the positive power $4$ that:
$$(1-x^{11})^{4} = \sum_{k=0}^{4} \binom{4}{k}(-1)^k x^{11k}$$
So $(1)$ becomes
$$\left(1 -\binom{4}{1}x^{11} + \binom{4}{2}x^{22} - \binom{4}{3}x^{33} + \binom{4}{4}x^{44} \right)\left(\binom{3}{0} +\binom{4}{1}x + \binom{5}{2}x^2 + \ldots\right)\tag{2}$$
And we still want the coefficient of $x^{10}$. But terms with $x^{11}$ or more we cannot use from the left hand side when multiplying out, so we only get the term where we use $1$ from the left hand sum and $\binom{13}{10}$ (the coefficient of $x^{10}$) from the right hand sum.
So the answer is $\binom{13}{10} = 286$. Thanks to the (generalised) binomial formula and geometric series.
When you multiply out $$(1+x+x^2+\cdots +x^{10})^4$$ you get terms of the form $$x^{a_1}x^{a_2}x^{a_3}x^{a_4}$$ where $a_1,a_2,a_3,a_4 \in \{0,1,\ldots, 10\}$ and you want $a_1+a_2+a_3+a_4=10$. Example, you take $x^0$ from the first three terms and $x^{10}$ from the last term would correspond to $a_1=a_2=a_3=0, a_4=10$.
So, how many solutions does this have? This is the stars and bars problem. As others have said, the answer is $$\dbinom{10+4-1}{4-1} = 286$$ Look up the stars and bars problem for more information if this method is easier for you to understand.