Generating Functions

Generating functions (Fall 2021) are a powerful tool for analyzing sequences and combinatorial problems by converting them into series. Given a sequence a_0,a_1,a_2,\ldots of numbers, its ordinary generating function is the power series \sum_{n=0}^\infty a_nz^n. For many sequences of combinatorial interest, this series can be evaluated in closed form. For instance, if a_n is the nth Fibonacci number, then the generating function is \frac{z}{1-z-z^2}. This generating function can be used to determine a closed-form expression for the Fibonacci numbers, known as Binet’s formula. A modification of the ordinary generating function is the exponential generating function, defined by \sum_{n=0}^\infty a_n\frac{z^n}{n!}. Generally, ordinary generating functions are well-suited for studying unlabeled structures, whereas exponential generating functions are well-suited for studying labeled structures.

There is a beautiful grammar of generating functions that allows us to convert from constructions of sequences to operations on generating functions. A typical example is the case of the Bell numbers B_n. This is the number of set partitions, i.e. ways of splitting the numbers 1,2,\ldots,n into disjoint nonempty unordered subsets; the first few Bell numbers are 1, 1, 2, 5, 15, 52. The exponential generating function for the Bell numbers has a remarkable closed-form expression: \sum_{n=0}^\infty B_n\frac{z^n}{n!}=e^{e^z-1}. What is especially impressive is that it is possible to deduce this closed formula without doing any calculation at all; it follows from general principles about how to build up exponential generating functions.

Another application of generating functions is to studying random objects. For instance, given a typical tree (of some type) with n nodes, what is the average length of a path from the root vertex to a randomly selected vertex? Multivariate generating functions give us good techniques for answering such questions.

So far, all this can be done using only formal properties of the generating function, without ever plugging in values for the variables but just by looking at the coefficients. But generating functions gain even more power when we start substituting values for the variables. In particular, the analytic properties of the generating function tell us about the growth rate of the coefficients: the location and type of the first singularity of the generating function dictates the main term of the growth rate of the sequence. For instance, the ordinary generating function for the celebrated Catalan numbers is \sum_{n=0}^\infty C_nz^n=\frac{1-\sqrt{1-4z}}{2z}. The first singularity of the generating function is at z=\frac{1}{4}, which implies a growth rate on the order of 4^n. However, the type of singularity, i.e. the square root, gives finer information about the growth rate and tells us that it is actually \frac{4^n}{n^{3/2}}. All this is completely general and can be used to determine asympototics of a wide range of combinatorially-interesting sequences.

Some knowledge of calculus will be assumed in this class, at the level of formally integrating and differentiating functions, especially power series.

This class will meet on Tuesday and Wednesday evenings. It is tentatively scheduled to meet from September 21 — December 1 from 6:30–8:30 PM, with a break the week of November 23–24. However, this schedule is subject to change due to ongoing uncertainty regarding the COVID-19 pandemic. Applications for this class are due July 25th. After that, we will continue to accept more applications on a rolling basis while space remains. Click here to apply!