Generating functions for combinatorics

Solution 1:

There is a very basic introduction available online at http://courses.csail.mit.edu/6.042/fall05/ln11.pdf

You might also find the following link helpful http://www.mathdb.org/notes_download/elementary/algebra/ae_A11.pdf

These notes give you a basic idea of how generating functions are useful for solving simple counting problems. Wilf's Generatingfunctionology is highly recommended if you want a more advanced and in depth treatment of the subject.

Solution 2:

I'd also recommend Wilf's Generatingfunctionology. It is available online. If you like it, do Wilf the courtesy of buying a copy.

Solution 3:

Flajolet and Sedgewick's Analytic Combinatorics is dense, but equips you with amazing tools to construct, manipulate, and extract information from generating functions. I also found the relevant chapters of Stanley's Enumerative Combinatorics (both volumes) extremely helpful.

Generating functions happen to be a favorite topic of mine, so I've written several posts on the subject on my blog. You might want to start at this post, which builds to an explanation of the Polya enumeration theorem, and a few years ago I wrote up these notes which might be useful.

There are in fact a few general principles, but I have enormous difficulty concisely describing them.

Solution 4:

To add to the other answers. The utility of generating functions goes further than counting-combinatorics. They are a basic tools for dealing with discrete functions, in particular with linear difference equations - and these frequently appear, typically as recursions, when solving many counting problems, or when dealing with discrete probabilities, etc.

A note for those who come from engineering: generating functions are very connected to the Z transform (an elemental tool in discrete Signal Processing) -arguably they are exactly the same thing, just different terminology - but the math and the concept is the same. And, to add further connections (perhaps further confusion?), the Z transform can be thought as the discrete version of the Laplace transform - and also as a generalization of the discrete Fourier transform.