# Generating functions for combinatorics

I have no formal education in generating functions, but, based on another question, I have seen that they can be powerful for combinatorics.

Are there a few general principles for using generating functions to construct counting arguments (e.g. counting the number of subsets or number of total orderings) that can be remixed to count different quantities?

I've been trying to read Concrete Mathematics (Graham, Knuth, Patashnik), but the topic spans several chapters and over 100 pages. At the moment, I just have patience to learn the gist of the combinatorics applications of generating functions. Maybe later I'll go back and get an extensive education from GKP.

-

There is a very basic introduction available online at http://courses.csail.mit.edu/6.042/fall05/ln11.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.

-
the MIT lecture notes are fantastic. Thank you! – dsg May 15 '11 at 3:24

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

-
"do Wilf the courtesy of buying a copy." I am not sure how much that benefits Wilf. I think that is doing more of a favor to the publishing company. – Eric Naslund May 14 '11 at 22:52
It may be worth inserting a link to Generatingfunctionology – Henry May 14 '11 at 23:18
A good point. But there are worse publishers to give your money to than A K Peters. – Michael Lugo May 14 '11 at 23:40

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.

-
Flajolet and Sedgewick's Analytic Combinatorics is truly a fantastic book. I'm having trouble putting it down! – dsg May 15 '11 at 10:26
@dsg: yes, it is really marvelous. You may not have heard, but Flajolet recently passed away (blog.computationalcomplexity.org/2011/03/…, rjlipton.wordpress.com/2011/03/27/philippe-flajolet-1948-2011) so you might be interested in reading a little about him. – Qiaochu Yuan May 15 '11 at 10:36

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.

-