The Gateway to Computer Science Excellence
+24 votes
3.3k 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 ?
in Combinatory by Boss (28.8k points)
retagged by | 3.3k views

3 Answers

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

by Veteran (57.2k points)
selected by
+4
Thanks for your detailed answer.

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

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

+2

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

+1
Got it!!
+26

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

+5
great !
+1

@mcjoshi  ADD it as an answer !

+2
Added:)
0
Manish explain your solution . I didnt get that.
0
Which part you didn't get ?
0
@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.
0

@Debashish excellent answer!

But I have a doubt what mcjoshi said he was trying i.e finding coefficient of x20 in (1+x2+x3+......+x10)(1+x2+..........+x20)2, is also correct right?

0

@Debashish Deka sir please explain this part

How to get??

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

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

If A = {x} why not select x?

So, all odd powers of x will be missing (=0) while selecting from A = {x}

and another part

But we have no such issue with y and z, Their generating functions   are 1/(1−x)

please explain sir

0

@srestha and @Debashish  Deka  and @ mcjoshi 

the right answer is 231??

please correct me if I'm  wrong

0
ans 121
0

@srestha 

How to solve second last step??

please explain 

$\frac{1}{2}$ *$\sum_{r=0}^{20}$(-1)$^{r}$ (r+2)(r+1)

=$\frac{1}{2}$ * 242


= 121

0

@dd @mcjoshi

Sir, if we try to make some changes such as

$3x+y+z=20$ then does the equation changes like this:

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

$Or$

if $3x+2y+z=20$ then like this:

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

0
Your answer answered many of my questions.....Great..
0
+35 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}$

by Boss (28.8k points)
+1
why using even odd concept.
+1
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 !!
+11 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

by Active (4.2k points)
+1
what if the equation be like 2x+3y+4z=20 will your trick works in this question..??
0
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
50,737 questions
57,356 answers
198,482 comments
105,253 users