summation

Let S denote the set of all triples (i, j, k) of positive integers where i + j + k = 17. Compute :
SUMMATION (x*y*z) ,
for all (i,j,k) belonging to set S

5 Answers

341
Hari Shankar ·

You are looking for the coefficient of x17 in

(x+2x^2+3x^3+.....)(x+2x^2+3x^3+.....)(x+2x^2+3x^3+.....)

or coeff of x14 in

(1+2x+3x^2+.....)(1+2x+3x^2+.....)(1+2x+3x^2+.....)

Now, recognize (1+2x+3x^2+.....)=(1-x)^{-2}

Hence we need to find coeff of x14 in (1-x)^{-6} which is

\binom {19}{6}

1
samagra Kr ·

but the ans is 19C5

1
samagra Kr ·

sir ,whats the logic behind this?

341
Hari Shankar ·

Oops! I stumbled at the last step. The coeff of x14 in (1-x)-6 is

\binom {19}{5}

This is derived from the theory of generating functions, which was first employed by Euler. But for this you dont need to read up generating functions, just try to follow the argument here.

First look at this question: Find all non-negative solutions for the equation x+y+z = 15. You can of course count by looking at the different solutions for various values of x. If x = 0, then y+z = 15 which has 16 solutions and so on.

But there is a more efficient method. Consider the following expression where each factor is an infinite series (rigorously called a formal series)

(1+x+x^2+....)(1+x+x^2+...)(1+x+x^2+...).

Now we can set up a one-one correspondence between the solutions to the given equation and the number of ways we can obtain the term x15. Remember that every term in the product is obtained by multiplying three terms, one from each bracket.

Now, if (i,j,k) is a particular solution, then map it to the expression x^i x^j x^k. You can easily see that this is a one-one correspondence. but notice that x^i x^j x^k = x^{i+j+k} = x^{15}. That means every solution set contributes a term of x15 to the expression.

That means all you have to do is count the number of times x15 appears, i.e. the coefficient of x15 in the expression. Using the identity in formal series \frac{1}{1-x} = 1+x+x^2+...

that means we have to find the coefficient of x15 in (1-x)-3.

Now, we can tackle a variation, that is positive integral solutions to x+y+z=15.

But that is a small step away using our approach. Just look at the expression

(x+x^2+x^3+...)(x+x^2+x^3+...)(x+x^2+x^3+...) = x^3 (1-x)^{-3}

In other words you now have to find the coefficient of x^{12} in (1-x)^{-3}.

Now the problem you posed has another variation. You are asking to add up the product ijk for every solution. Now can you see why the expression given in my post does the job?

It does so because now you are making every such combination xixjxk that gives rise to x17 contribute the term ijk to the expansion and in effect you are therefore adding up the product ijk for every solution.

The next step is to be able to identify the series in a way that makes it accessible to computation. This will need you to know binomial theorem for negative indices.

This is a powerful tool and knowing how to manipulate generating functions can make many complicated seeming problems a cake walk!

1
samagra Kr ·

thank you sir

Your Answer

Close [X]