Chapter 10 Recursions and generating functions

Generating functions are a useful tool in combinatorics and probability. We will again a see a few easy examples to illustrate the basic ideas. This is part of what is known as ’analytic combinatorics’. A basic reference is [Wilf 2005] and for more advanced reading in analytic combinatorics, see [Flajolet and Sedgewick, Melczer 2021, Pemantle and Wilson 2023].

AIM - To understand sequence $a_0,a_1,\mathrm{\dots }$. IDEA Investigate analytically the function $f(x)={\sum }_{n\ge 0}{a}_n{x}^n$ for $x\in ℝ$. Similarly use multivariate functions to understand sequences such as $a_{m,n},m\ge 0,n\ge 0$ and $a_{l,m,n},l,m,n\ge 0$. Sometimes it is of use to consider variable $z\in ℂ$. We shall mainly focus on real functions.

The ordinary generating function (OGF) is the function

$$f(x)=\sum _{n\ge 0}{a}_n{x}^n.$$

Sometimes it is more useful to consider the exponential generating function (EGF)

$$f(x)=\sum _{n\ge 0}{a}_n\frac{x^n}{n!}.$$

We shall not be explicit about the domain of the functions. It is necessary only that the functions are well-defined in some open interval. The specific interval is not of relevance to us.