1. {0, 1, 2, 3, 4,………….}
2. {1, 2, 3, 4, 5,………….}
3. {2, 2, 2, 2, 2,………….}
4. {0, 0, 0, 1, 1, 1, 1……}

Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 8 Marks

Year: May 2014

1. {0, 1, 2, 3, 4,………….}

   Assume the generating function

   $f(x)=a_0+a_1x+a_2 x^2+a_3 x^3+……$

   But, the given sequence is {0, 1, 2, 3, 4,…………}. Using this sequence, the expression above becomes

   f(x)$=x+2x^2+3x^3+4x^4…… \\ =x(1 +2x+3x^2+4x^3+……) \\ =x(1-x)^{-2}$

   Accordingly, $f(x) = x(1-x)^{-2}$ is the generating function for the given sequence {0, 1, 2, 3, 4,…………}

2. {1, 2, 3, 4, 5,………….}

   Assume the generating function

   $f(x)=a_0+a_1x+a_2 x^2+a_3 x^3+……$

   But, the given sequence is {1, 2, 3, 4,…}. Using this sequence, the expression above becomes

   f(x)$=1 +2x+3x^2+4x^3+…… =(1-x)^{-2}$

   Accordingly, $f(x)= (1-x)^{-2}$ is the generating function for the given sequence {1, 2, 3, 4,…}

3. {2, 2, 2, 2, 2,………….}

   Assume the generating function

   $f(x)=a_0+a_1x+a_2 x^2+a_3 x^3+……$

   But, the given sequence is {2, 2, 2, 2, 2,…………}. Using this sequence, the expression above becomes

   f(x)$=2 +2x+2x^2+2x^3+…… \\ =2(1+x+x^2+x^3+…….) \\ =2(1-x)^{-1}$

   Accordingly, $f(x) = 2(1-x)^{-1}$ is the generating function for the given sequence {2, 2, 2, 2, 2,…………}

4. {0, 0, 0, 1, 1, 1, 1……}

   Assume the generating function

   $f(x)=a_0+a_1x+a_2 x^2+a_3 x^3+……$

   But, the given sequence is {0, 0, 0, 1, 1, 1, 1……}. Using this sequence, the expression above becomes

   f(x)$=0 +0x+0x^2+x^3+x^4+x^5+x^6+…… \\ =x^3+x^4+x^5+x^6+…… \\ =x^3 (1+x+x^2+x^3+…….) \\ =x^3 (1-x)^{-1}$

   Accordingly, $f(x) = x^3 (1-x)^{-1}$ is the generating function for the given sequence {0, 0, 0, 1, 1, 1, 1…}