GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
302 views

Find the coefficient of $x^{16}$ in $(x^{2} + x^{3} + x^{4} + x^{5})^{5}$


Please solve this question using Generating functions step by step ?

asked in Combinatory by Veteran (14.7k points)  
retagged by | 302 views
x^4 x^5 ? addition in between ? why nt use latex ? easy to read
I think 135

Assuming polynomial as (x2+x3+x4+x5)5

we can rewrite it as (x2(1+x+x2+x3))5 = x10(1+x+x2+x3)5

now we have to find coefficient of x6 from (1+x+x2+x3)5 --------------( becoz x6 * x10 = x16 )

now we can imagine above polynomial as 5 boxes ( becoz whole power is 5 ) and each box can have either 0 or 1 or 2 or 3 items in it and final addition of all items of the boxes will be 6. That  means

x1 + x2 + x3 + x4 + x5 = 6  such that 0 <= xi <= 3 where i can be 1 to 5

so complement of above equation will be atleast one of the xi will have value greater than 3

so to find this first we will have to find total ways of doing this and then deduct those ways which include items greater than 3 in the boxes.

total ways = 6+5-1C6 = 10C6 = 210

since least value greater than 3 is 4. That means the complement equation will have only one xi with least value 4

So consider x1 is greater than 3, that means 4 <= x1

rewriting the equation

x1 + 4 + x2 + x3 + x4 + x5 = 6

x1 + x2 + x3 + x4 + x5 = 2

number of ways of doing this = 2+5-1C2 = 6C2 = 15

similarly x2 or x3 or x4 or x5 can also be greater than 3

so total ways = 15 * 5 = 75

 

So required answer = total ways - complemented ways = 210 -75 =135

 

210 -75 =135 correct
@Digvijay You should add this as an answer. Good explanation.
Nice explanation  .. please add this as answer.

1 Answer

+3 votes
Best answer

we can use Pascal's triangle for finding this binomial expansion then higher order terms are neglected.

answered by Veteran (11.6k points)  
selected by
this is what i was looking for as an explanation! thank you!

Related questions

+1 vote
1 answer
2
0 votes
0 answers
3


Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1502 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1416 Points

  5. Niraj Singh 2

    1391 Points

  6. Debashish Deka

    1246 Points

  7. Rupendra Choudhary

    1194 Points

  8. rahul sharma 5

    1158 Points

  9. Arjun

    956 Points

  10. srestha

    950 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1386 Points

  3. junaid ahmad

    502 Points

  4. Debashish Deka

    414 Points

  5. sudsho

    410 Points


23,373 questions
30,079 answers
67,406 comments
28,396 users