The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
1.5k 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 (27.6k points)
retagged by | 1.5k views

3 Answers

+24 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 (57.4k points)
selected 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:)
Manish explain your solution . I didnt get that.
Which part you didn't get ?
@Debashish @mcjoshi

isnot $= \binom{2}{0} - \binom{3}{1} + \binom{4}{2} - \binom{5}{3} + \binom{6}{4} - \binom{7}{5}...+\binom{22}{20}$ calculation time consuming? :(

Any way to calculate quickly.
+18 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 (27.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 !!
+10 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 (4k 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.


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

28,981 questions
36,818 answers
91,200 comments
34,706 users