GATE CSE
First time here? Checkout the FAQ!
x
+11 votes
753 views
Find the number of integral soultions of $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 (22.2k points)  
edited by | 753 views

3 Answers

+18 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 (37.5k points)  
edited by
Thanks for your detailed answer.

Now trying to understand Generating Functions.
gen function is awesome !
Great explanation. Thanks.

I have understood your procedure, but how you are deriving this:-

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

? how many ways can  we collect $k$ indistinguishable objects from a given set into a distinguishable place. If the answer to this question is = $m$.

then $m*x^{k}$ will be a member of the generating function.

Got it!!

Debashish, Just came up with another way.

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

great !

@mcjoshi  ADD it as an answer !

Added:)
+11 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 (22.2k points)  
+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.2k 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 Jan 2017
  1. Debashish Deka

    9660 Points

  2. sudsho

    5554 Points

  3. Bikram

    5280 Points

  4. Habibkhan

    4878 Points

  5. Vijay Thakur

    4498 Points

  6. Arjun

    4418 Points

  7. saurabh rai

    4236 Points

  8. Sushant Gokhale

    4140 Points

  9. Kapil

    3848 Points

  10. santhoshdevulapally

    3808 Points

Monthly Topper: Rs. 500 gift card

19,443 questions
24,221 answers
53,871 comments
20,372 users