in Combinatory retagged by
25,521 views
57 votes
57 votes
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.
in Combinatory retagged by
25.5k views

4 Comments

Very good method @Sourav.Sharma

1
1
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,)
1
1

$\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.

 

1
1

17 Answers

70 votes
70 votes
Best answer

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 \\ $

edited by

4 Comments

please explain 1st method
1
1

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

1
1

this will helps u a lot

1
1
55 votes
55 votes

$(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$ = x12)

$(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.

edited by

4 Comments

@Rajesh Pradhan sir can you upload that sheet again it's not showing up

0
0
edited by
1
1
Formula from Generating functions is  used

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

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.$

edited by

4 Comments

@Verma Ashish

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

It is also given in rosen.

3
3
Thanks.. :)

Now i understand..
2
2
12 votes
12 votes
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
edited by

4 Comments

What is the formula for

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

I am felling difficult to get coefficient 6 and 10

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

There you go.

11
11
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true