Why are generating functions useful?

I was under the mistaken impression that if one could find the generating function for a sequence of numbers, you could just plug in a natural number n to find the nth term of the sequence. I realize now that I was confusing this with a closed form formula.

So if that is not the case, then what is the point of generating functions? How do they make understanding counting sequences easier? For example, suppose I had a problem where I wanted to count how many ways I could buy n pieces of apples, oranges, and pears given that I want an even number of apples, an odd number of oranges, and at most 3 pears. This would be the number of nonnegative integer solutions to a+b+c=n with a even, b odd, and 0c3. This is the same as the coefficient of xn in the product
(1+x2+x4+)(x+x3+x5+)(1+x+x2+x3)=11x2x1x21x41x

But what good is that? I don’t see how this is much better. Also, with use of exponential generating functions, it seems the choice of monomials we use as place holders for the terms of the sequence can be arbitrary. Then then nth term of the sequence is just the coefficient of the nth monomial that you’ve chosen to build the generating function with. What is the real advantage of doing things like this? Many problems I see tend to ask me find the generating function, but then I’m rarely asked to do anything with it.

Answer

Closed form formulas are overrated. When they exist, generating function techniques can often help you find them; when they don’t, the generating function is the next best thing, and it turns out to be much more powerful than it looks at first glance. For example, most generating functions are actually meromorphic functions, and this means that one can deduce asymptotic information about a sequence from the locations of the poles of its generating function. This is, for example, how one deduces the asymptotic of the partition numbers.

In your particular example, the generating function is rational, so it has a finite number of poles. That means you can use partial fraction decomposition on it to immediately get a closed form.

You might be interested in reading my notes on generating functions, which have several examples and which I hope will be enlightening. The first basic thing to grasp is that manipulating generating functions is much easier than manipulating sequences, but the power of generating functions goes much deeper than this. For a really thorough discussion I highly recommend Flajolet and Sedgewick’s Analytic Combinatorics, which is available for free online.

Attribution
Source : Link , Question Author : Dani Hobbes , Answer Author : leonbloy

Leave a Comment