Combinatorics (Fall 2010)/Generating functions

Generating Functions

In Stanley's magnificent book Enumerative Combinatorics, he called the generating function "the most useful but most difficult to understand method (for counting)".

The solution to a counting problem is usually represented as some [math]\displaystyle{ a_n }[/math] depending a parameter [math]\displaystyle{ n }[/math]. Sometimes this [math]\displaystyle{ a_n }[/math] is called a counting function as it is a function of the parameter [math]\displaystyle{ n }[/math], but we can also treat it just as a infinite series:

[math]\displaystyle{ a_0,a_1,a_2,\ldots }[/math]