Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $0\leq c\leq 3$. This is the same as the coefficient of $x^n$ in the product $$ (1+x^2+x^4+\cdots)(x+x^3+x^5+\cdots)(1+x+x^2+x^3) = \frac{1}{1-x^2}\cdot\frac{x}{1-x^2}\cdot\frac{1-x^4}{1-x}$$

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 $n$th term of the sequence is just the coefficient of the $n$th 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.

share|improve this question
1  
Have you looked at the standard books dealing with the subject? –  Mariano Suárez-Alvarez Mar 7 '11 at 3:39
11  
This online book answered that question for me: math.upenn.edu/~wilf/gfologyLinked2.pdf. Until recently I hadn't had much contact with generating functions, and had the same question that you're asking, but I got the hang of them after reading the first half of that book. For example take a look at Example 2 on page 35, which shows some of the power of the generating function approach. The main point, I think, is that things that look complicated for sequences are straightforward for the corresponding functions -- such as multiplying and dividing by functions. –  joriki Mar 7 '11 at 3:42
    
@Mariano, I've dabbled in a handful of combinatorics/discrete math books, but I never really saw the point of them, even in those texts. @joriki, thanks for the link, I've actually heard of the book, but I didn't know it was available. Thanks. –  Hobbie Mar 7 '11 at 3:45
2  
I think of the powers of $x$s as bins, and the coefficients as keeping track off how many of a given sized bin appear in all the combinations you want. It seems almost magical that the multiplication law of partitions exactly tracks that of polynomial multiplication. –  Uticensis Mar 7 '11 at 4:00
1  
Generating functions can often be used to find exact or asymptotic formulas for the nth term. In your example, you could find the partial fraction decomposition and use that to derive a formula for the nth term. –  Dave Radcliffe Mar 7 '11 at 4:02

6 Answers 6

up vote 20 down vote accepted

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.

share|improve this answer
5  
That first sentence is very true. (Not that the rest isn't, but anyway.) I remember myself being a bit surprised (quite a while ago already) to realise that $x=\sqrt{2}$ isn't really easier than "positive solution to $x^2-2=0$" to deal with. In fact you would just be making it harder to understand for yourself what it really is. I guess the same thing applies here. –  Myself Mar 7 '11 at 13:22
    
Not only can you get asymptotics of the sequence, but also finite prefixes (by series expansion done by computer algebra). That allows to quickly check whether a solution is correct, and it might even give you the answer to your question ("How many X of size $N$ are there?"). –  Raphael Jun 9 '12 at 14:11
1  
The mit.edu link is dead; but googling for the filename gave math.berkeley.edu/~qchu/TopicsInGF.pdf . I'll accept the concern of the OP though: for finding the actual exact term for a particular fixed $n$, the generating function is usually not any more useful (when solving by hand) than ignoring GFs entirely. In cases simple enough that one is willing to find partial fraction expansions by hand, it is usually simpler to solve the problem directly. Here is a particularly absurd contrast. Finding asymptotic estimates is great though. –  ShreevatsaR Dec 22 '13 at 10:17

Have you read Generatingfunctionology by Herbert Wilf? The book is loaded with methods and techniques based on generating functions for solving a number of different problems. I guess the book can answer your question better than I could.

I feel that generating functions are powerful because they allow you to use tools from calculus and analysis to solve problems in areas such as discrete mathematics and combinatorics, where such tools don't seem readily applicable.

Edit: I just wanted to add one more point. Suppose you have translated the problem from the sequence to the generating function and you don't see any simple closed form solutions, you could use Wolfram Alpha to make absolutely sure. Wolfram alpha can easily expand out expressions involving large polynomial terms and will often give you a series expansion if it exists in closed form.

share|improve this answer

To answer your question for the example you state:

$$ \frac{1}{1-x^2} \cdot \frac{x}{1-x^2} \cdot \frac{1-x^4}{1-x} = (x+x^2 +x^3 + x^4)(1-x^2)^{-2} $$

By binomial theorem (yes, it is valid for negative exponents too) we get that this is equal to

$$ (x + x^2 + x^3 + x^4) \left(\sum_{j=0}^{\infty} (-1)^j {-2 \choose j} x^{2j}\right)$$

Can you now figure out a formula for the coefficient of $\displaystyle x^n$, thus solving your problem?

share|improve this answer
    
Thanks Moron, this sounds interesting. So I distributed the $x$s into the sum, and I get the coefficient of $x^n$ to be $$\sum_{k=1}^4(-1)^{(n-k)/2}\binom{-2}{(n-k)/2}$$ but I'm not sure how valid that is, since I could end up getting imaginary numbers. What's the correct way to go about it? –  Hobbie Mar 7 '11 at 4:41
    
@Hobbie: You need to choose only those $k$ for which $(n-k)/2$ is an integer. –  Aryabhata Mar 7 '11 at 4:53
    
So something like: $$\sum_{k\colon 1\leq k\leq 4,\ (n-k)/2\in\mathbb{Z}} (-1)^{(n-k)/2}\binom{-2}{(n-k)/2}?$$ –  Hobbie Mar 7 '11 at 4:58
    
@Hob: I believe that works. –  Aryabhata Mar 7 '11 at 7:32

I like the book "Analytic Combinatorics" by Philippe Flajolet and Robert Sedgewick Part A. It doesn't only show a way how you translate combinatorical problems in terms functional relations of generating functions (the show that unlabelled structures relate to ordinary generating functions, and labelled structures relate to exponential generating functions), but it also provides ways (asymptotic expansion, ...) such that you can actually calculate something.

share|improve this answer

When trying to understand a counting situation, the best thing to have is a closed form formula, a function that is easily calculable by well known methods ('closed-form' is a bit slippery in meaning, but usually means, without any recursion, but there's room for disagreement over whether summations or products are allowed (though factorial is often allowed). From such functions, it is usually straightforward to determine approximations and asymptotics and to combine with other other functions.

The next best thing is a recurrence. It allows calculation often in a very straightforward manner with no approximation needed. But recurrences are a bit inscrutable; it's very difficult to simplify or read off properties directly from the recurrence (whereas closed form is very easy to understand).

Somewhere between these two, generating functions allow ease in combinatorial manipulation (multiplying two ogfs means that one is getting an ordered pair of the objects the gfs describe). Also there are analytical techniques that allow extraction of asymptotics from gfs. And ostensibly one can get values for $f(n)$ from the gf by differentiating it $n$ times and evaluating at 0.

Wilf's generatingfunctionology, as mentioned in the comments, is the place to go for getting these techniques for gfs.

share|improve this answer

They are quite useful in problems 137 and 140 at Project Euler, though you have to take them seriously as convergent series.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.