Generating Functions

Generating functions encode sequences as power series, providing a powerful tool for solving combinatorial problems.

Definition

For a sequence $a_{0}, a_{1}, a_{2}, \dots$ , the generating function is:

G (x) = a_{0} + a_{1} x + a_{2} x^{2} + \dots = \sum_{n = 0}^{\infty} a_{n} x^{n}

For the sequence $1, 1, 1, \dots$ :

G (x) = 1 + x + x^{2} + x^{3} + \dots = \frac{1}{1 - x} (for | x | < 1)

Generating functions solve recurrence relations, count partitions, and model probability distributions.