Let’s start with a simple problem: You are playing with your kid and (s)he wants you to assemble a train rake with two types of coaches. : Goods (G) and passengers (P) coaches. How many different train rakes of size n (Tn), you can build with the constraint that no two passenger (P) coaches are connected together.
To find the closed form for Tn let’s start with simple and small cases:
T0 = 1 as there is only one way of build train rakes of size 0 ie pick no coach at all….
T1 = 2 namely {P, G}
T2 = 3 namely {PG, GP, GG}
Are we reaching to a simple closed form Tn = n+1? Before concluding at it let’s look at next case T3:
T3 = 5 viz {PGP, GGP, PGG, GPG, GGG}
And now this is giving us some pattern. Observe that, first two entries in T3 can be built by attaching GP to all entries in T1 and next three entries of T3 can by created by attaching G to all entries of T2. This means, for assembling a train of size n, take a train of size n-1 and simply attach a G coach or take a train of size n-2 and attach G and then P coach. So total number of train rakes of size n is equal to:
Tn = Tn-1 + Tn-2: for n≥2 with T0 = 1 and T1 = 2 (1)
Remember something similar to equation (1)? Fibonacci numbers? The recurrence for Tn is very similar to that of Fibonacci numbers with the exception of initial values T0 and T1. This gives us a very simple closed form for Tn as:
Tn = Fn+2 :where Fn+2 is (n+2)th Fibonacci number (2)
To confirm that equation (2) is indeed a closed form for Tn let’s try to find out closed form for Tn using another method. This method is nothing but manipulation of infinite sequence. Consider sum of all possible rakes:
SUM = ф+P+G+PG+GP+GG+PGP+GGP+PGG+GPG+GGG+………… (3)
Where ф is the null rake for n=0. As we said earlier, since this is a manipulation of infinite series we will not be worried about the convergence of the infinite series, addition / multiplication of these combinatorial objects etc. With these assumptions equation (3) can be written as:
SUM = ф+P+(ф+P+G+PG+GP+GG+………….)G+( ф+P+G+PG+GP+GG+………….)GP
In the above equation ф is multiplicative identity since фG = Gф = G
= ф+P+SUMG+SUMGP
SUM(ф-G-GP) = ф+P
(One can confirm the above equation by actually subtracting SUMG and SUMGP from SUM)
This implies:
SUM = ф+P / ф-G-GP
We will go one step further and simplify the steps by paying no attention to the type of coach by replacing G/ P by z and ф by 1.
SUM = 1+z/ 1-z-z2
SUM = 1/1-z-z2 + z/1-z-z2 (4)
SUM = 1/1-z-z2 + z/1-z-z2 (4)
Now z/ 1-z-z2 is called generating function for Fibonacci numbers as coefficient of znin the expansion of this closed form gives the nth Fibonacci number Fn. One can try expanding this formula using the rule:
1/ 1-z = 1+z+ z2+ z3+………………
Hence z/ 1-z-z2 = z(1+(z+z2) + (z+z2)2+ (z+z2)3+………)
= z(1+z+ z2+ z2+ 2z3+ z4+ z3+…………)
= z+ z2+2 z3+3 z4+……….. (5)
From equation (5) we get F0 = 0; F1 = 1; F2 = 1; F3 = 2; F4 = 3 and so on….
Similarly 1/1-z-z2 is generating function for Fn+1 ie Fibonacci numbers shifted by one place.
Thus equation (4) is generating function for number of rakes with given constraints. Ie
GF(number of train rakes) = GF(Fn+1) + GF(Fn) (6)
=> Tn (coefficient of zn in LHS) = Fn+1 (coefficient of zn in first series)+Fn (coefficient of zn in second series)
=> Tn = Fn+1 + Fn
=> Tn = Fn+2 (7)
We are able to find the closed form for the number of rakes using generating functions (7) which matches with the closed form calculated using recurrence equation(2).
So what are generating functions? Formally generating function for the infinite sequence a0, a1, a2,….., ak,….of real numbers is the infinite series:
Generally, while dealing with generating functions, we do not evaluate G(z) by substituting some real value for z. It’s another way of finding a solution to the problem and hence we ignore the issue of convergence. Instead we treat generating function as a formal power series with z as a place holder for a coefficient we are interested in. In above example, coefficient an in generating function (6) provides us number of train rakes of size n and this is what we are interested in calculating.
We also observed that we can have closed forms for generating function. This means generating functions is a single quantity representing the whole sequence and it converts the problem of sequences into the problem of functions. This way it enhances our ability of problem solving since we can apply all the knowledge of dealing with functions to the problems of sequences. This makes generating functions a very important and useful concept in the field of Mathematics/ Computer Science.
