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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ the MIT lecture notes are fantastic. Thank you! $\endgroup$ – dsg May 15 '11 at 3:24
  • 4
    $\begingroup$ The links no longer work, is there any way you could post new ones? $\endgroup$ – Jeremy Baziw Apr 20 '17 at 15:56
13
$\begingroup$

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

$\endgroup$
  • 7
    $\begingroup$ "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. $\endgroup$ – Eric Naslund May 14 '11 at 22:52
  • 1
    $\begingroup$ It may be worth inserting a link to Generatingfunctionology $\endgroup$ – Henry May 14 '11 at 23:18
  • 2
    $\begingroup$ A good point. But there are worse publishers to give your money to than A K Peters. $\endgroup$ – Michael Lugo May 14 '11 at 23:40
  • $\begingroup$ Thanks for putting in the link, quanta. I googled "Generatingfunctionology;" the download page comes out right on top of Google's list. $\endgroup$ – ncmathsadist May 15 '11 at 0:50
8
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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