21
$\begingroup$

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?

If the answer is not amenable to this forum, where can I learn more?

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.

4 Answers 4

3

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.

13

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

  • 0
    Thanks for putting in the link, quanta. I googled "Generatingfunctionology;" the download page comes out right on top of Google's list.2011-05-15
13

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.

  • 4
    The links no longer work, is there any way you could post new ones?2017-04-20
8

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.

  • 0
    @dsg: yes, it is really marvelous. You may not have heard, but Flajolet recently passed away (http://blog.computationalcomplexity.org/2011/03/phillipe-flajolet-passed-away.html, http://rjlipton.wordpress.com/2011/03/27/philippe-flajolet-1948-2011/) so you might be interested in reading a little about him.2011-05-15