GATE CSE
First time here? Checkout the FAQ!
x
+11 votes
1k views
Find the number of integral solutions of $\large 2x + y + z = 20$ with $x, y, z >= 0$ ?

I tried finding coefficient of $x^{20}$ in $(1 + x^2 + x^3 + ...... + x^{10})(1+ x^2 + .......... + x^{20})^2$, but it gives wrong answer ?
asked in Combinatory by Veteran (24.6k points)  
edited by | 1k views

3 Answers

+20 votes
Best answer

The generating function for choosing elements from a union of disjoint sets is the product of the generating functions for choosing from each set. (page15)

Example :

Equation : $x + y = 10$ and we are asked to find out the number of non negative integral solution of this equation.

We can assume A = $\left \{ x \right \}$ and B = $\left \{ y \right \}$ as two sets and each having a single element.

We need to select n(=0,1,2,3,4...) elements from set A with repeatation allowed.

How can we select 0 element from A ? => 1 way. (selecting no element is one way)

How can we select 1 element from A ? => 1 way. (select x itself)

How can we select 2 element from A ? => 1 way. (select x and x)

How can we select 3 element from A ? => 1 way.(select x,x, and x) . etc...

So, generated sequence of selection of n ( = 0,1,2,3,4..) elements from one element set A with repeatation is (1,1,1,1,1,1,1,.....)

Corresponding generating function is = $1x^0+1.x^1+1.x^2+1.x^3+1.x^4+....\infty$ = $\frac{1}{1-x}$

All powers of x are reflected in the sequence. starting from 0 to $\infty$ with coefficient 1.(because in each case no of ways = 1)

Similarly with set B, generating function is = $1x^0+1.x^1+1.x^2+1.x^3+1.x^4+....\infty$ = $\frac{1}{1-x}$

Product of the above two generating function is the generating function of the sequence generated when n (=0,1,2,3,4...) elements are selected from the set $\left \{ x,y \right \}$

So, resultant generating function = $\frac{1}{(1-x)^2}$ and solution is coefficient of $x^n$ where n = 10.

 

Some more frequent generating function :

           Sequence                                $\leftrightarrow$             Generating function

Worth reading on generating function .

 


Now, coming to the quesiton asked :

$2x + y + z = 20$

if we ask the same quesitons for the set containing x = $\left \{ x \right \}$ = A (one element set)

How can we select 0 element from A ? => 1 way. (selecting no element is one way)

(so, coefficient of $x^0$ is = 1)

How can we select 1 element from A ? => 0 way. (we can not select single x)

(so, coefficient of $x^1$ is = 0)..etc..

How can we select 2 element from A ? => 1 way. (select two x)

How can we select 3 element from A ? => 0 way.(we can not select three x) . etc...

So, all odd powers of x will be missing (=0) while selecting from A = $\left \{ x \right \}$. Sequence of numbers generated from selection of n (=0,1,2,3,4...) elements from A is (1,0,1,0,1,0,1,0......) and the corresponding generating function is

$$\begin{align*} &= 1+x^2+x^4+x^6+x^8+... \\ &= 1+ (x^2)^1 + (x^2)^2 + (x^2)^3 + (x^2)^4 +....\\ &= \frac{1}{1-x^2}\\ \end{align*}$$

But we have no such issue with y and z, Their generating funcitons are $\frac{1}{1-x}$

Multiplying all three generating functions we get the resultant generating function for the sequence generated while selecting n (=0,1,2,3,4..) elements from the set $\left \{ x,y,z \right \}$.

$$\begin{align*} &= \frac{1}{1-x^2}\frac{1}{1-x}\frac{1}{1-x} \\ &= \frac{1}{1-x^2}\frac{1}{(1-x)^2} \\ &= \frac{1}{1+x}\frac{1}{(1-x)^3} \\ \end{align*}$$

Now final task is to find the coefficient of $x^{20}$ in this expression.

No issue, just a little bit of math :)

$$\begin{align*} &= \left [ x^{20} \right ]\frac{1}{(1+x)}\frac{1}{(1-x)^3} \\ &= \left [ x^{20} \right ]\left [ \sum_{r=0}^{\infty }(-1)^rx^r \right ]\left [ \sum_{r=0}^{\infty }\binom{3+r-1}{r}x^r \right ] \\ &= \left [ x^{20} \right ]\left [ \sum_{r=0}^{\infty }(-1)^rx^r \right ]\left [ \sum_{r=0}^{\infty }\binom{r+2}{r}x^r \right ] \\ &= \binom{2}{0} - \binom{3}{1} + \binom{4}{2} - \binom{5}{3} + \binom{6}{4} - \binom{7}{5}...+\binom{22}{20}\\ \text{Or,} \\ &=\sum_{r=0}^{20}(-1)^r\binom{r+2}{r}\\ &=\frac{1}{2}\sum_{r=0}^{20}(-1)^r(r+2)(r+1)\\ &=\frac{1}{2}*242 = 121 \\ \end{align*}$$

 


more example:

NOTE:

1. $1+x+x^2+x^3+.....x^n = \frac{1-x^{n+1}}{1-x}$

2. $\frac{1}{(1-x)^n} = \sum_{r=0}^{\infty}\binom{n+r-1}{r}.x^r$

3. $\left [ x^{20} \right ]$ means coefficient of $x^{20}$ of the whole expression.

answered by Veteran (45.6k points)  
edited by
great !

@mcjoshi  ADD it as an answer !

Added:)
Manish explain your solution . I didnt get that.
Which part you didn't get ?
+14 votes

$2x + y + z = 20$

$y + z = 20 - 2x = \;even$

So, for $y + z$ to be even either both $y$ and $z$ are even (or) both are odd.

When both are even : $y = 2a$ and $z = 2b$

$2x + 2a + 2b = 20$

$x + a + b = 10$

Number of non-negative integral solutions $= \binom {10 + 3 -1}{3-1} = \binom{12}{2} = 66$

When both are odd : $y = 2a + 1 $ and $z = 2b + 1$

$2x + 2a + 1 + 2b + 1 = 20$

$x + a + b = 9$

Number of non-negative integral solutions $ = \binom {9+3-1}{3-1} = \binom{11}{2} = 55$

Total non-negative integral solutions $\color{maroon}{= 66 +55 = 121}$

answered by Veteran (24.6k points)  
why using even odd concept.
It's not a standard way of doing these type of questions. It's just that it worked for this problem by breaking problem into cases and then adding up.

Debashish's answer above is standard way to go !!
+9 votes

Given Equation: 2x+y+z=20 where x,y,z>=0

the point is equation a1+a2+a3+............+ak=n 

will have differenet no of solution= k+n-1C n .

value of x can range from 0 to 10 .

so when (x=0) then y+z=20 , No of solution = 21

(x=1) then y+z=18 , No of solution =19

..........................................................

till (x=10) then y+z=0 , No of solution =1

so total no of solution = (1+3+5+7+9+.............+21) = 11/2(1+21)= 121

answered by Loyal (3.5k points)  
what if the equation be like 2x+3y+4z=20 will your trick works in this question..??
But there will an issue with the final summation, sometimes no standard summation series arise.


Top Users Apr 2017
  1. akash.dinkar12

    3366 Points

  2. Divya Bharti

    2536 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1584 Points

  8. Prashant.

    1462 Points

  9. Arunav Khare

    1444 Points

  10. Kapil

    1414 Points

Monthly Topper: Rs. 500 gift card

22,072 questions
28,030 answers
63,191 comments
24,128 users