GATE CSE 2016 | Set 1 | Question: 26

Question

The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.

Comments

The problem can read as :

You are given 3 buckets and you need to pick out 12 items, but each bucket only allows you to pick at least 3 items in one go (not less than that)

We can easily shift the origin from 3 to 0 (as 3 items are always compulsory to pick). So 9 will be picked anyway. We can only decide on the remaining 3.

And now we only need to pick 3 items (and we are allowed to pick any number of items starting from 1, 2,)

---

$\color{red}{\text{Detailed Video Solution:}}$ GATE 2016 Generating Function, Click HERE.

$\color{red}{\text{Generating Function Complete Playlist,}}$ ALL GATE Questions, Extended Binomial Theorem: https://youtube.com/playlist?list=PLIPZ2_p3RNHiu4mkROrhREYsslvp2lL5l 

Knowing the “Extended Binomial Theorem” makes Generating Function topic extremely easy. Watch the above playlist to learn everything, with Proof & Variations.

 

---

Method 1 by Praveen sir says (its actually a cool way to solve it))

when we solve whole cube and opens power We will get $x^{12}$ as:

1. $(x^{4})^{3}$ having coefficient $\frac{3!}{3!} = 1$ (distributing 3 such that all three items are the same)

2. $(x^{3})^{2}(x^{6})$ having coefficient $\frac{3!}{2!1!} = 3$ (distributing 3 such that 2 items are the same and 1 is different)

3. $(x^{3})(x^{4})(x^{5})$ having coefficient $\frac{3!}{1!1!1!} = 6$ (distributing 3 such that all three are different)

So it is $1 + 3 + 6 = 10$

Answer 1

we will get $x^{12}$ as
 

1. $(x^4)^3$ having coefficient $^3C_0=1$
2. $(x^3)^2(x^6)$ having coefficient $^3C_1=3$
3. $(x^3)(x^4)(x^5)$ having coefficient ${^3C_2} \times {^2C_1} =6$

So it is $10$

Second Method:

$\left [ {\color{red}{\bf x^{12}}} \right ] \left ( x^3 + x^4 + x^5 + x^6 + \dots \right )^3$
$  \left [ {\color{red}{\bf x^{12}}} \right ] \left [ x^3\left ( 1 + x^1 + x^2 + x^3 + \dots \right ) \right ]^3 $
$ \left [ {\color{red}{\bf x^{12}}} \right ] \left [ x^9\left ( 1 + x^1 + x^2 + x^3 + \dots \right )^3 \right ] $
$ \left [ {\color{red}{\bf x^{3}}} \right ] \left [ \left ( 1 + x^1 + x^2 + x^3 + \dots \right )^3 \right ] $
$ \left [ {\color{red}{\bf x^{3}}} \right ] \left [ \left ( \frac{1}{1-x} \right )^3 \right ]$
$ \left [ {\color{red}{\bf x^{3}}} \right ] \left [ \sum_{k=0}^{\infty}\binom{3+k-1}{k}x^k \right ]$
$ \text{Now , put k = 3}$
$ \text{Coefficient of }\left [ {\color{red}{\bf x^{3}}} \right ] = \binom{2+3}{3} = 5C3 = 5C2 = 10 $

---

$ \left [ {\color{red}{\bf x^{12}}} \right ] \left ( x^3 + x^4 + x^5 + x^6 + \dots \right )^3 \Rightarrow \bf 10 \\ $

Comments

please explain 1st method

---

for generating functions refer this site http://discretetext.oscarlevin.com/dmoi/section-27.html

---

this will helps u a lot

Answer 2

$(x^3 + x^4 + x^5 + x^6 + ... )^3 = (x^9) (1 + x^1 + x^3 + x^4 + x^5 + ...)^3$  

From second term we need to find the coefficient of $x^3$   bcz ($x^3$ *$x^9$ = $x^{12} $)

$(1 + x^1 + x^3 + x^4 + x^5 + ...)^3 = (\frac{1}{1-x})^3 = (1-x)^-3 = 1 + 3x + 6x^2 + 10x^3 +...$

Clearly, coefficient of $x^3$ is $10$

Note:- Actually this was ans. from Sudarshana Tripathy which i thought that very easy to understand by anyone. but it was in the one of the comment in one of the ans  here which may not be come under eye of everyone..so i thought that it is worth to put as answer.

Comments

@vizzard110

Look for this:

https://gateoverflow.in/1175/gate2005-50?show=326979#c32697

---

Formula from Generating functions is  used

i.e =>  (1-x)^(-n) = [(n-1+k) c (k)] * (x^k)

---

Nice solution

Answer 3

The coefficient of $x^{12}\: \text{in}\: (x^{3}+x^{4}+x^{5}+x^{6}+\dots)^{3}$

$\implies(x^{3}+x^{4}+x^{5}+x^{6}+\dots)^{3}$ 

$\implies[x^{3}(1+x+x^{2}+x^{3}+x^{4}+\dots)]^{3}$ 

$\implies[x^{3}(1+x+x^{2}+x^{3}+x^{4}+\dots)]^{3}$ 

$\implies x^{9}[1+ x+x^{2}+x^{3}+x^{4}+\dots]^{3}\rightarrow(1)$

Let generating sequence $(1,1,1,1,1,1,1\dots)$

write the generating function:

$G(x) = 1+x+x^{2} + x^{3} + x^{4} +\dots$

$G(x) = \dfrac{1}{(1-x)}  \:\: [\text{ Sum of infinite series}]$

Put this value in equation $(1),$ and get

$\implies$  $x^{9}\left[\dfrac{1}{(1-x)}\right]^{3}$

$\implies$  $x^{9}.\dfrac{1}{(1-x)^{3}}$

$\implies$  $x^{9}.(1-x)^{-3}$

Apply Binomial Theorem

•  $(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}(a)^{n-k}.(b)^{k}$
• $(a+b)^{-n}=\sum_{k=0}^{\infty}\binom{-n}{k}(a)^{-n-k}.(b)^{k}$
• $(a+b)^{-n}=\sum_{k=0}^{\infty}\binom{n+k-1}{k}(-1)^{k}(a)^{-n-k}.(b)^{k}$

Now i find the $(1-x)^{-3}=\sum_{k=0}^{\infty}\binom{3+k-1}{k}(-1)^{k}(1)^{-3-k}.(-x)^{k}$

$\implies$$x^{9}.(1-x)^{-3}= x^{9}.\sum_{k=0}^{\infty}\binom{3+k-1}{k}(-1)^{k}.(-x)^{k}$

Put $k =3$,we get $x^{12},$

$\implies x^{9}.\binom{3+3-1}{3}(-1)^{3}.(-x)^{3}$

$\implies x^{9}.\binom{5}{3}(-1)^{3}.(-1)^{3}.(x)^{3}$

$\implies x^{9}.\binom{5}{3}(-1).(-1).(x)^{3}$

$\implies x^{9}.\binom{5}{3}.x^{3}$

$\implies \binom{5}{3}.x^{3}x^{9}.$

Coefficient of $x^{12}\: \text{is} : \binom{5}{3}$   

 $\implies \dfrac{5!}{(5-3)!.3!}$

 $\implies \dfrac{5!}{2!.3!}$

 $\implies \dfrac{5.4.3!}{2!.3!}$

 $\implies \dfrac{5.4}{2.1 }$

 $\implies10$

So, the correct answer  is $10.$

Comments

@Verma Ashish

for  proof, you can check https://gateoverflow.in/205464/extended-binomial-coefficients

It is also given in rosen.

---

Thanks.. :)

Now i understand..

---

Thank you Bhaiya. Very neat answer

 

Answer 4

We know the formula $(a+b)^n$

                              =$_{0}^{n}\textrm{C} a^0 b^n + _{1}^{n}\textrm{C} a^1b^n-1+......$

Similarly,

1) $(_{1}^{3}\textrm{C}) (x^3)^1 (x^4+x^5+x^6+..)^2$

Now for,

$(x^4+x^5+x^6+..)^2$

=$((x^4+x^5)+(x^6+....))^2$

=$(_{0}^{2}\textrm{C}) (x^4+x^5)^0(x^6+..)^2$

 

2) $(x^3+x^4+x^5+x^6+..)^3$

=$((x^3)+(x^4+x^5+x^6+....))^3$

=$(_{0}^{3}\textrm{C}) (x^3)^0(x^4+x^5..)^3$

=$(_{0}^{3}\textrm{C}) (x^3)^0(_{3}^{3}\textrm{C})(x^4)^3(x^5+x^6.....)^0$

3) $(x^3+x^4+x^5+x^6+..)^3 =(_{1}^{3}\textrm{C}) (x^3)^1(_{1}^{2}\textrm{C}) (x^4)^1(_{1}^{1}\textrm{C}) (x^5)^1(x^6+..)^0$

Now addition of coefficients are =(1)+(2)+(3)=10

Comments

What is the formula for

$(1-x)^{-3}$

I am felling difficult to get coefficient 6 and 10

plz tell

---

summation 0 to infinity (3+r-1 Cr * x^r)

---

There you go.

Answer 5

= [ x³ ( 1 + x + x² + x³ + ....................... ) ]³

= x⁹ ( 1 + x + x² + x³ +.......................)³

= x⁹ (1 / ( 1 - x ) )³

= x⁹ ( 1 / ( 1 - x )³ )

= x⁹ ( ( 1 - x )^-3 )

= x⁹ ( 1 + (3)x + ( (3*4) / (1*2) ) x² + ( (3*4*5) / (1*2*3) ) x³ +...................................)

= x⁹ + 3x¹⁰ + 6x¹¹ + 10x¹² +........................................................

Answer = 10

Answer 6

[x¹²](x³ + x⁴ + x⁵ +x⁶ +...)³ = [x³](1 + x + x² + x³ +x⁴ +...)³ = [x³]((1-x)^-1)³ =  [x³](1-x)^-3

 ^= -3C₃(-1)³ = ⁵C₃(-1)³(-1)³ =  ⁵C₃ = 10