Generating functions

A generating function is a way to represent a sequence of numbers as the coefficients of a power series. For a sequence $a_0, a_1, a_2, ext{...}$, its generating function is $G(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + ext{...}$. Generating functions help us solve counting problems by turning them into algebraic problems with polynomials or power series.

Important properties

• The coefficient of $x^n$ in the generating function gives the $n$th term of the sequence.

• Generating functions can be added, multiplied, or manipulated to model different combinatorial situations.

• Multiplying generating functions corresponds to combining choices in counting problems (the convolution of sequences).