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 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.

share|improve this question

4 Answers 4

up vote 11 down vote accepted

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.

share|improve this answer
1  
the MIT lecture notes are fantastic. Thank you! –  dsg May 15 '11 at 3:24

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.

share|improve this answer
1  
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

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

share|improve this answer
7  
"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
1  
It may be worth inserting a link to Generatingfunctionology –  Henry May 14 '11 at 23:18
2  
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
    
Thanks for putting in the link, quanta. I googled "Generatingfunctionology;" the download page comes out right on top of Google's list. –  ncmathsadist May 15 '11 at 0:50

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.

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.