Generating Functions · Generating Functions

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

Generating functions are one of the most powerful and beautiful methods of discrete mathematics, developed by Euler in the 1750s. Generating functions allow analyzing sequences of numbers as follows:

  1. from the world of sequences we transition to the world of functions (more precisely, formal power series);
  2. in this world, we can use various formal transformations of functions;
  3. using the corresponding transformations, we bring the function to the desired form, expand it into a series — and return to the world of sequences.
This approach allows obtaining explicit formulas for various counting problems without using any combinatorial ideas and is therefore a universal tool. For example, as we have seen, proofs of the explicit formula for Catalan numbers require nontrivial combinatorial ideas. We will see that with the help of generating functions, this formula can be derived mechanically. We will also show how to derive explicit formulas for various combinatorial quantities and recurrence relations.