retagged by
9,013 views

3 Answers

Best answer
44 votes
44 votes

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.

selected by
37 votes
37 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}$

12 votes
12 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

Answer:

Related questions

4 votes
4 votes
2 answers
1
0 votes
0 votes
1 answer
2
1 votes
1 votes
0 answers
3
air1ankit asked Oct 9, 2017
400 views
generating function shifted Fibonacci sequence (what we actually do while finding generating function)