Generating Functionology


To understand Generating functions, Let us take a simple example.
How do you represent the series of numbers, 1, 3, 3, 1, 0, 0, 0 as a coefficients of a polynomial?
Let us try.
\(1 + 3x + 3{x^2}\) + \({x^3} + 0{x^4}\) + \(0{x^5} + ...\)
\( \Rightarrow 1 + 3x + 3{x^2} + {x^3}\) = \({\left( {1 + x} \right)^3}\)
So, the sequence of numbers 1, 3, 3, 1 can be expressed as a polynomial \({\left( {1 + x} \right)^3}\).
This is called generating function.
The general notation of the generation function is
\(f\left( x \right) = {a_0} + {a_1}x + {a_2}x + \). . . + \({a_n}{x^n}\)
Let us try to represent the following sequence of numbers as generating function.
A. \(1,~1,~1,~1,~1. . .\) = \(1 + x + {x^2} + {x^3} + ...\) = \(\dfrac{1}{{1 - x}}\)
B. \(1,~1,~1,~1,~1,~1,~0,~0,~0,~0,...\) = \(1 + x + {x^2} + {x^3} + {x^4} + {x^5}\) = \(\dfrac{{1 - {x^6}}}{{1 - x}}\)
C.  \({}^{100}{C_0}\), \({}^{100}{C_1}\), \({}^{100}{C_2}\), . . .,\({}^{100}{C_{100}}\) = \(1 + {}^{100}{C_1}\left( x \right)\) + \({}^{100}{C_2}\left( {{x^2}} \right)\) + ...\({ + ^{100}}{C_{100}}\left( {{x^{100}}} \right)\) = \({\left( {1 + x} \right)^{100}}\)

Extended Binomial Coefficient concept:

We know that \({}^n{C_r}\) = \(\dfrac{{n\left( {n - 1} \right)\left( {n - 2} \right)....\left( {n - (r - 1)} \right)}}{{r!}}\)
For example, \({}^{10}{C_4} = \dfrac{{10\left( {10 - 1} \right)\left( {10 - 2} \right)\left( {10 - 3} \right)}}{{4!}}\)
We can apply the above concept to any real \(n\).
For example, To find the value of \({}^{ - 5}{C_{20}}\)
\({}^{ - 5}{C_{20}}\) = \(\dfrac{{ - 5\left( { - 5 - 1} \right)\left( { - 5 - 2} \right)....\left( { - 5 - (20 - 1)} \right)}}{{20!}}\) = \(\dfrac{{ - 5\left( { - 6} \right)\left( { - 7} \right)....\left( { - 24} \right)}}{{20!}}\) = \(\dfrac{{24.23.22.....5}}{{20!}}\) = \({}^{24}{C_{20}}\)
Similarly, \({}^{ - 5}{C_{19}} = \dfrac{{ - 5. - 6. - 7.... - 23}}{{19!}}\) = \( \dfrac{{23.22.......5}}{{19!}}\) = \({}^{23}{C_{19}}\)

So we can derive a general formula for this: \({{}^{ - n}{C_r} = {\left( { - 1} \right)^r}\times{}^{(n + r - 1)}{C_r}}\)
(Note: you need not bother about the negative sign.  The expression is positive whether 'r' is even or odd).

Question 1:
There are 30 identical textbooks, to be distributed among the 50 students, and each student may get more than one textbook. How many ways are there to distribute the 30 textbooks among the 50 students?
Solution:
Each student may receive 0, 1, 2, ....  textbooks.
Generating function for one student = \(1 + x + {x^2} + ...\)
GF for all students = \({\left( {1 + x + {x^2} + ...} \right)^{50}}\)
So we have to find \({x^{30}}\) coefficient in the above expression.
\({\left( {1 + x + {x^2} + ...} \right)^{50}}\) = \({\left( {\dfrac{1}{{1 - x}}} \right)^{50}}\) = \({\left( {1 - x} \right)^{ - 50}}\)
So required answer = \({}^{ - 50}{C_{30}}\) = \({\left( { - 1} \right)^{30}}.{}^{(50 + 30 - 1)}{C_{30}}\) = \({}^{79}{C_{30}}\)

Right Shifting *:
Right shifting means adding some zeroes before the sequence.
For example, take a sequence, \(1,~1,~1,~1,~1. . .\).  Converting it to \(0,0,0...(k - zeroes),1,1,1,...\)
What happens when you add \(k\) zeroes?
\(0,0,0...(k - zeroes),1,1,1,...\) = \((0.1 + 0.x + 0.{x^2}\) + . . . + \(0.{x^{k - 1}})\) + \({x^k} + {x^{k + 1}} + ...\)
We are adding \(k\) terms from \(1\) to \({x^{k - 1}}\) whose coefficients are zero.  So the first term whose coefficient is \(1\) starts from \({x^k}\).
Therefore, \(0,0,0...(k - zeroes),1,1,1,...\) = \({x^k} + {x^{k + 1}} + ...\)
= \({x^k}\left( {1 + x + {x^2} + ...} \right)\)
= \({x^k} \times \dfrac{1}{{1 - x}}\)
= \(\dfrac{{{x^k}}}{{1 - x}}\)
*As a rule of thumb, when you are adding one zero, multiply the sequence with \(x\), when you are adding two zeroes, multiply the sequence with \({x^2}\), or adding \(k\) zeroes means multiply with \({x^k}\).

Question 2:
To understand the above rule, let us try to derive the GF for Fibonacci series. 1, 1, 2, 3, 5, 8, 13. . .
Solution:
The above series general form is \({a_{n + 2}} = {a_{n + 1}} + {a_n}\)
\({a_{n + 2}} - {a_{n + 1}} - {a_n} = 0\)
So we make two series by adding one zero and two zeroes before the sequence and subtract the series from the original.
\( f(x) = 1, 1, 2, 3, 5, . . .  \)
\( x.f(x) = 0, 1, 1, 2, 3, . . .  \)
  \( x^2.f(x) = 0, 0, 1, 1, 2, 3 \)
Therefore,  \(f(x) - x.f(x) - {x^2}.f(x) = 1\)\( + \left( {1 - 1+0} \right)\) + \(\left( {2 - 1 - 1} \right) + ...\)
⇒ \( f(x)\left( {1 - x - {x^2}} \right) = 1\)
⇒ \( f(x) = \dfrac{1}{{1 - x - {x^2}}}\)
If you perform long division of the above expression, the coefficients of the series gives us 1, 1, 2, 3, 5, . . .

Scaling rule: 
Multiplying each term in a generating functions by a constant \('c'\) makes the coefficients \('c'\) times.
Example:
Take the sequence \(1,~1,~1,~1,~1. . .\).
This can be expressed as,
\(f\left( x \right) = 1 + x + {x^2} + {x^3} + ... = \dfrac{1}{{1 - x}}\)
Now multiplying the above expressing by \(2\), we get
\(2 \times f\left( x \right) = 2 + 2x + 2{x^2} + 2{x^3} + ... = \dfrac{2}{{1 - x}}\)

Question 3:
Using generating functions, find \({a_n}\) in terms of \(n\) if \({a_0} = 2\) and \({a_{n + 1}} = 3{a_n}\)
Solution:
Here (n+1) term is 3 times of previous term.  We add one zero before the series and multiply the series by 3 and subtract it.
⇒ \( G(x) = {a_0} + {a_1}x + {a_2}{x^2} + ...\)
⇒ \( x.G(x) = 0 + {a_0}x + {a_1}{x^2} + ...\)
⇒ \( 3x.G(x) = 0 + 3{a_0}x + 3{a_1}{x^2} + ...\)
⇒ \(  G(x) - 3x.G(x) = 2 + ({a_1} - 3{a_0})x + ...\)
⇒ \( G(x)\left( {1 - 3x} \right) = 2 + ({a_1} - 3{a_0})x + ...\)
\({a_1} - 3{a_0} = {a_2} - 3{a_1} = ...{a_{n + 1}} - 3{a_n} = 0\)
\(G(x) = \dfrac{2}{{1 - 3x}}\)
\(G(x) = 2\left[ {1 + 3x + {{\left( {3x} \right)}^2} + ...} \right]\)
General term in the above sequence = \({a_n} = {2.3^n}\)

Question 4:
Using generating functions, find \({a_n}\) in terms of \(n\) if \({a_0} = 1\), \({a_1} = 2\) and \({a_{n + 2}} = 5.{a_{n + 1}} - 4.{a_n}\)
Solution:
Given, \({a_{n + 2}} = 5.{a_{n + 1}} - 4.{a_n}\)
Therefore, \({a_{n + 2}} - 5.{a_{n + 1}} + 4.{a_n} = 0\)
We have to modify the sequence in such a way that, we have to subtract 5 times of the previous term, and add 4 times of the next to previous term.
⇒ \( G(x) = {a_0} + {a_1}x + {a_2}{x^2} + ...\)
⇒ \( -5x.G(x) = 0 - 5{a_0}x -5{a_1}{x^2} + ...\)
⇒  \(4{x^2}.G(x) = 0 + 0 + 4{a_0}{x^2} + 4{a_1}{x^3} + ...\)
⇒ \(\left( {1 - 5x + 4{x^2}} \right)G\left( x \right)\) = \({a_0} + \left( {{a_1} - 5{a_0}} \right)x\) + \(\left( {{a_2} - 5{a_1} + 4{a_0}} \right){x^2} + ...\)
⇒ \(\left( {1 - 5x + 4{x^2}} \right)G\left( x \right)\) = \(1 + \left( {2 - 5 \times 1} \right)x + 0{x^2} + 0.{x^3}...\)
⇒ \(\left( {1 - 5x + 4{x^2}} \right)G\left( x \right) = 1 - 3x\)
⇒ \(G\left( x \right) = \dfrac{{1 - 3x}}{{1 - 5x + 4{x^2}}}\)

Addition rule:
It is very useful to form another series by the summation of two known series.
Let us take two sequences \(1,~1,~1,~1,~1. . .\) and \(1,-1,~1,-1,~1. . .\).
We know that \(1,~1,~1,~1,~1. . .\) = \(1 + x + {x^2} + {x^3} + ...\) = \(\dfrac{1}{{1 - x}}\)
and \(1,-1,~1,-1,~1. . .\) = \(1 - x + {x^2} - {x^3} + ...\) =  \(\dfrac{1}{{1 + x}}\)
Addition of the two sequences gives us,
\(2,~0,~2,~0,~2. . .\) = \(\dfrac{1}{{1 - x}} + \dfrac{1}{{1 + x}}\) = \(\dfrac{2}{{1 - {x^2}}}\)

Derivative rule:
Generating functions behave like regular polynomials.  So we can easily apply calculus rules.
Suppose, Natural numbers (\(1,~2,~3, . . .\)) can be generated by differentiating the sequence \(1,~1,~1,~1,~1. . .\).
\(1 + x + {x^2} + {x^3} + ... = \dfrac{1}{{1 - x}}\)
\(\dfrac{d}{{dx}}\left( {1 + x + {x^2} + {x^3} + ...} \right)\) = \(\dfrac{d}{{dx}}\left( {\dfrac{1}{{1 - x}}} \right)\)
⇒ \(1 + 2x + 3{x^2} + ...\) = \(\dfrac{1}{{{{\left( {1 - x} \right)}^2}}}\)

Product Rule:
Take two sequences, \(f\left( x \right)\) = \({a_0} + {a_1}x + ... + {a_n}{x^n}\)
\(g\left( x \right)\) = \({b_0} + {b_1}x + ... + {b_n}{x^n}\)
Let \(f\left( x \right).g\left( x \right) = {c_0} + {c_1}x + ... + {c_n}{x^n}\)
To find the coefficients we multiply the above polynomials.
Generating functionology product rule

From the above table you can see that
\({x^0}\) coefficient = \({c_0}\) =  \({a_0}{b_0}\)
\({x^1}\) coefficient = \({c_1}\) = \({a_0}{b_1} + {a_1}{b_0}\)
. . .
Therefore, \({c_n}\) = \({a_0}{b_n} + {a_1}{b_{n - 1}} + {a_2}{b_{n - 2}}\) + . . . + \({a_n}{b_0}\)

Convolution Rule:
 Let A(x) be the generating function for selecting items from set A, and let B(x) be the generating function for selecting items from set B, Let C(x) be the generating function for selecting items from set C, so on. If A, B and C. . .  are disjoint, then the generating function for selecting items from the union A ∪ B ∪ C . . . is the product A(x).B(x).C(x). . ..
Though this rule appears to be daunting, the first solved example explains the usage of this rule.