An Introduction To Enumeration Using Generating Functions

Posted by Yehonatan on 2/28/18 6:03 PM

Math Blog.jpg

In the year 1202, Italian mathematician Leonardo Fibonacci published Liber Abaci (Book of Calculations). Though its most significant contribution was to bring to Europe the Hindu-Arabic number system that we all use today, it also contained a curious thought experiment about the reproductive patterns of rabbits, which gave rise to one of the most famous sequences in math that would entertain and tantalize generations of mathematicians to come.

Do Mathematicians Dream of Immortal Rabbits?

The problem goes like this. Say that a rabbit comes of age when it is one year old. Having reached this mark of adulthood, each adult rabbit gives birth to one baby rabbit each year. Assume we start at time 0 with a single baby rabbit. How many rabbits will there be at a given point in time?

To illustrate, we can begin by looking at the first few years. After one year passes, the baby rabbit grows to an adult. There is still 1 rabbit, who is now ready to have kids. In year two, our rabbit has a baby so the population grows to 2. We now have one adult and one baby. In year three, the adult gives birth again and last year's baby reaches adulthood. We now have 3 rabbits-- two adults and one baby. Next year, the two adults each have a baby so the population grows to 5 rabbits. And so on.

The sequence charting the rabbit population thus begins

1,1,2,3,5,...

We denote the nth element of the sequence by Screen Shot 2018-02-28 at 4.50.12 PM.png. To test your understanding, try to determine the next few terms.

Fibonacci's model of rabbit populations is not particularly sophisticated or accurate. For one thing, it imagines that a rabbit can reproduce all on its own. Much more glaringly, it conveniently ignores death. But by this point you probably figured that the rabbits are only a pretext. Mathematicians dream of immortal rabbits in order to study interesting math.

So what is interesting here? Let's take another look at the sequence:

1,1,2,3,5,8,13,21,...

You might notice a pattern: each term is precisely the sum of the previous two! How come? There's a simple reason. Each given year, the population consists of those rabbits who were around last year, plus the number of babies who are newly born:

This year's population = Last year's population + number of newborns

But how do we count the newborns? Well, newborns are precisely identified by their parents (since each rabbit has a unique parent in our simplified model). The eligible parents are exactly those who were in existence two years ago (since they must have had enough time to first become an adult and then give birth). So there we have it: the number of newborns exactly equals the population of two years ago. We can then update our equation:

This year's population = Last year's population + The population of two years ago

Or in a more concise form:

Screen Shot 2018-02-28 at 4.51.45 PM.png

With the caveat that this formula only really makes sense if Screen Shot 2018-02-28 at 4.52.36 PM.png

This kind of formula is called a recurrence relation: it relates each term of the sequence to previous terms. It gives us a practical way of generating the sequence: each time simply add the previous two terms. We can now forget about rabbits, babies and adults, and simply follow an arithmetical rule. You can play with that to write the next few terms of the sequence.

Rate of growth

We now understand how the Fibonacci sequence behaves locally, that is, how each term relates to the ones that came immediately before it. But what if we wanted to understand the long-term behavior? One basic way to assess that is the rate of growth. How quickly does the rabbit population grow?

Here is one way to get a handle on the growth of the Fibonacci sequence. Start with the recurrence relation

Screen Shot 2018-02-28 at 4.51.45 PM-1.png

Now notice that Screen Shot 2018-02-28 at 4.56.26 PM.png since the sequence is always increasing. Plugging in this inequality above,

Screen Shot 2018-02-28 at 4.57.22 PM.png

This is telling us that Screen Shot 2018-02-28 at 4.58.12 PM.png more than doubles every two years. A quantity that doubles every fixed number of years is exponential. Thus, the Fibonacci sequence, though modest at first, in fact increases exponentially.

In search of an explicit equation

We have gained some insight into the long-term behavior of the Fibonacci sequence, but only in the form of a rough lower bound. In some sense we still lack a fully satisfactory understanding of the Fibonacci numbers. What if we wanted to get the 50th term of the sequence? We could compute it using the recurrence relation, but that would entail first calculating all the previous 49 terms before we get the answer. Is there a single explicit equation that describes the nth Fibonacci number without relying on the previous elements of the sequence?

There is certainly no immediately apparent answer. Fibonacci himself failed to come up with such an explicit formula in his book. The theory of linear difference equations deals with this type of question, but we will instead use the tool of generating functions, in order to showcase its power. But we must first take a short detour to the topic of power series.

Power Series

A power series is like a super-powered version of a polynomial. While a polynomial is a modest expression such as Screen Shot 2018-02-28 at 4.59.50 PM.png a power series has infinitely many terms. For example, consider the power series

Screen Shot 2018-02-28 at 5.00.49 PM.png

or

Screen Shot 2018-02-28 at 5.01.35 PM.png

(where the ellipsis indicate that we keep going ad infinitum).

The first question that arises is, what does this even mean? How can you add together infinitely many terms? Indeed, if we tried to plug in x=1 into the above power series p(x), we get the infinite sum 1+1+1+..., which diverges to infinity. Even worse, if we try plugging in x=-1, we get the infinite sum 1-1+1-1+1-..., which I invite you to try to evaluate.

To avoid these tangles, we will be careful to refrain from thinking of power series as functions. We simply do not expect to be able to plug in a number and get out another number. Instead, a power series will be a formal expression, amounting simply to a choice of coefficient for each power Screen Shot 2018-02-28 at 5.02.46 PM.png

At first, this might seem like a useless invention, merely dressing up a sequence of coefficients in the garb of a polynomial. The crucial point, however, is that even while power series cannot be viewed as functions, we can still perform algebra with them just as we do with polynomials: we can add, subtract, multiply (and sometimes even divide) power series with each other.

To illustrate the interesting algebra that can be done with power series, let's start with the simple power series

Screen Shot 2018-02-28 at 5.03.29 PM.png

Consider what happens when we multiply by x:

Screen Shot 2018-02-28 at 5.04.16 PM.png

Observe that this is exactly the same as p(x), except missing a 1. That is,

Screen Shot 2018-02-28 at 5.05.07 PM.png

Factoring out Screen Shot 2018-02-28 at 5.05.53 PM.png, we get

Screen Shot 2018-02-28 at 5.06.33 PM.png

or

Screen Shot 2018-02-28 at 5.07.17 PM.png

That is,

Screen Shot 2018-02-28 at 5.08.11 PM.png

We have found a way to rewrite Screen Shot 2018-02-28 at 5.09.25 PM.png from an infinite expression into a simple fraction!

(Sidenote: I emphasized earlier that power series should not be thought of as functions. However, in the special case that -1<x<1, you can actually plug in x into the above equation and obtain a valid equation.

For example, Screen Shot 2018-02-28 at 5.10.24 PM.png

We can also attempt to go in the other direction, converting a quotient of polynomials into a power series. For example, consider a fraction of the form Screen Shot 2018-02-28 at 5.15.28 PM.pngWe can relate this to our previous example by factoring out a -r from the denominator:

Screen Shot 2018-02-28 at 5.16.20 PM.png

Screen Shot 2018-02-28 at 5.16.51 PM.png

Challenge: If you want to practice your power series chops, try deriving an expression for the more complicated power series Screen Shot 2018-02-28 at 5.18.04 PM.png. Hint: again, consider the difference Screen Shot 2018-02-28 at 5.18.42 PM.png What does this equal?

I promised that power series will help us figure out an explicit equation for the Fibonacci numbers. This is where generating functions come in. 

Generating Functions

The idea of generating functions is simple. In order to understand sequences, we can transform them into power series by turning the elements of the sequence into power series coefficients. For example, if we start with the sequence 1,1,1,1,..., its generating function is the power series

Screen Shot 2018-02-28 at 5.19.28 PM.png

which we studied in the last section. If we start with the Fibonacci sequence 1,1,2,3,5,...,  its generating function is the power series 

Screen Shot 2018-02-28 at 5.20.15 PM.png 
The hope is that, now that we converted the Fibonacci sequence Screen Shot 2018-02-28 at 5.21.00 PM.png into a power series Screen Shot 2018-02-28 at 5.21.27 PM.png we can use algebra as in the last section to gain additional insight about Screen Shot 2018-02-28 at 5.21.27 PM-1.png and then translate that back into insight about the sequence Screen Shot 2018-02-28 at 5.22.38 PM.png

Consider multiplying by Screen Shot 2018-02-28 at 5.23.06 PM.png

Screen Shot 2018-02-28 at 5.23.56 PM.png 
If you look in each column from the bottom up, you will notice that the coefficients of each Screen Shot 2018-02-28 at 5.24.47 PM.png term are consecutive Fibonacci numbers. But because each Fibonacci number is the sum of the previous two, that means exactly that each coefficient in the top row is the sum of the corresponding coefficients in the bottom two rows, with the exception of the lone 1 in the first row. That is,

Screen Shot 2018-02-28 at 5.25.17 PM.png

We took the recurrence relation which characterizes the Fibonacci sequence and turned it into an equation of power series! With some further algebraic manipulation, we solve:

Screen Shot 2018-02-28 at 5.26.17 PM.png

Again, using algebraic manipulation we turned a power series from an infinite sum to a compact expression as a fraction. But we can simplify even further. You may recall the technique of partial fractions: if we factor the polynomial Screen Shot 2018-02-28 at 5.27.53 PM.png into linear terms Screen Shot 2018-02-28 at 5.31.08 PM.png we can rewrite the fraction

Screen Shot 2018-02-28 at 5.35.18 PM.png 
for some numbers A and B.

We will determine these numbers later-- Screen Shot 2018-02-28 at 5.36.16 PM.pngbut first let's take a step back and ask, why does this help us? Remember, in the previous section we derived a simple expression for the power series given by the fraction Screen Shot 2018-02-28 at 5.37.46 PM.png namely 

Screen Shot 2018-02-28 at 5.38.16 PM.png

We thus obtain

Screen Shot 2018-02-28 at 5.39.15 PM.png

From this, we can read an expression for the Fibonacci numbers. Remember, Screen Shot 2018-02-28 at 5.40.08 PM.png is the coefficient of Screen Shot 2018-02-28 at 5.40.33 PM.png in the power series Screen Shot 2018-02-28 at 5.41.15 PM.png which, by above, is

Screen Shot 2018-02-28 at 5.42.10 PM.png

The explicit equation we've been looking for! It now remains to solve for the numbers Screen Shot 2018-02-28 at 5.44.14 PM.png and plug in. This is an exercise in algebra which you are encouraged to solve. I will spare you the details and skip straight to the final answer:

Screen Shot 2018-02-28 at 5.44.35 PM.png

At first glance, this might appear to be a very surprising answer. After all, the Fibonacci numbers Screen Shot 2018-02-28 at 5.45.21 PM.png are always whole numbers, and yet our formula above involves the decidedly unwhole quantity Screen Shot 2018-02-28 at 5.46.06 PM.png It turns out, however, that whenever we evaluate the formula for a specific value of n, all of the squareroots end up canceling out and we magically obtain a whole number. For example, if we plug in n=0, we get

Screen Shot 2018-02-28 at 5.46.41 PM.png

This solution conveys some of the power of generating functions. By converting the combinatorial sequence of interest into a power series, we can use algebra to massage it into a form from which we can more readily read off the coefficients. 

Rate of Growth, Revisited

In addition to the satisfaction of having arrived at an explicit solution for the Fibonacci numbers, the solution also gives us a more precise answer concerning the rate of growth of the Fibonacci numbers.

Let's take a closer look at the solution

Screen Shot 2018-02-28 at 5.47.42 PM.png

The two instrumental numbers here are Screen Shot 2018-02-28 at 5.48.40 PM.png The former is larger than 1 while the latter has absolute value less than 1, so the term Screen Shot 2018-02-28 at 5.50.05 PM.png increases exponentially while the term Screen Shot 2018-02-28 at 5.50.57 PM.png decreases exponentially, becoming negligably small for large n. So for large enough values of n, we can approximate 

Screen Shot 2018-02-28 at 5.51.42 PM.png

In fact this approximation holds fairly well even for small values of n. This means that the long-term rate of growth of the Fibonacci numbers is Screen Shot 2018-02-28 at 5.52.17 PM.pngapprox Screen Shot 2018-02-28 at 5.52.24 PM.png each year the population of rabbits is approximately multiplied by this rate. Incidentally, this number is known as the golden ratio, a ratio which has been known since antiquity for cropping up in many geometric constructions, and which is believed to be especially aesthetic, hence "golden". It is this number which drives the hidden engine of the Fibonacci numbers.

Do you need a mathematician like Yehonatan to help you through the most difficult problems?

Contact Us!