In this lecture we continue our long march towards Stirling’s formula. Let me begin by saying that, while we seem to be spending an absurd amount of time on this, Stirling’s approximation is being used as a case study in something much more general, Laplace’s method, and we will understand the general thing almost automatically once we understand the specific thing.

We return to the integral representation

In Lecture 2, we performed some elementary estimates which showed that, for all sufficiently small we have

where is a positive number depending on but not on This quantifies the intuition that the bulk contribution to the integral comes from a small neighborhood of the minimum of the action.

We now come to the problem of estimating this bulk contribution

The action

is holomorphic on the open unit disc and its Maclaurin series is

this series converging absolutely and uniformly on compact subsets of to the correct value In Lecture 2, we observed that if we throw away all terms in the series expansion of beyond the quadratic term, our integral -integral becomes the truncated Gaussian integral

which can then be replaced by a total Gaussian integral at the cost of introducing an exponentially small error,

this being beneficial because the total Gaussian integral can be exactly evaluated,

Thus, the remaining question is to quantify the error incurred by replacing

We now want quantify the error incurred by throwing away all terms of the action beyond its dominant (quadratic) term. For small we naturally expect this error to be a small number which decays as increases, but this decay turns out to be much slower than exponential and represents the main source of error in the approximation scheme we’re building.

To get started, we write

Next, we Maclaurin-expand the non-Gaussian part of the integrand, writing

where is the th derivative of at Assuming this series converges uniformly on indeed, it is the Maclaurin series of the function and we aren’t changing the location of singularities by subtracting an entire function. We can thus interchange the order of summation and integration, thereby obtaining

We have thus reduced the initial problem to two problems.

**Problem 1:** Compute the coefficients

**Problem 2:** Compute the integrals

We will solve Problem 1 today, and Problem 2 on Thursday (in case you’d like to think ahead).

Problem 1 is pure algebraic combinatorics, being a question about composition in the algebra of formal power series This question can be phrased in greater generality, as follows. Let

be elements of such that the constant term of is zero. Notice that we are writing these series as if their coefficients were the derivatives of analytic functions and at but we are not actually imposing any convergence conditions on them. Series of this form are often referred to as exponential generating functions. The composition

is well-defined. Let and expand

The problem is to understand the coefficients of in terms of the coefficients of and This problem was posed and solved by Hurwitz in the nineteenth century in connection with what is now a classical problem in enumerative geometry, namely the question of counting branched covers of the Riemann sphere with specified ramification data (I hope to touch on this problem more extensively later in the course).

**Exercise 1:** Compute the first few coefficients of by hand.

**Exercise 2:** Does it make sense to do this computation using the chain rule? Why or why not? Do you get correct formulas by this method?

Let’s consider first an easier problem, which well serve as a stepping stone. Consider two series

and let

be their product. It is then immediate that

This algebraic expression also has combinatorial meaning, which becomes clear if we sacrifice its elegance and rewrite it in the garish form

The enumerative meaning of this expression is the following. Suppose that is the number of combinatorial structures of Type A which can be built on and similarly is the number of combinatorial structures of Type B which can be built on Then, is the number of ways to build a hybrid combinatorial structure of Type AB on by choosing disjoint subsets and building a type A structure on and a Type B structure on This can be iterated: the product of exponential generating functions is an exponential generating function whose coefficients count the number of ways to select a list of disjoin subsets of whose union is and then build a Type A_j structure on for each

**Exercise 3:** Read this (easy), this (harder), or this (hardest).

We can now state the main theorem on composition of exponential generating functions, A partition of is a set of disjoint nonempty subsets of whose union is The elements of are called its blocks, and we denote by the number of blocks in Let denote the set of all partitions of

**Theorem (The Compositional Formula):** With notation as above, we have

*Proof:* Write

use the combinatorial expansion and reorganize the sum.

— Q.E.D.

**Corollary (The Exponential Formula):** If then

The combinatorial meaning of the Exponential Formula is the following: if is the exponential generating function for a class of “connected” combinatorial structures The Exponential Formula gets used all over the place — probabilists call it the moment-cumulant formula, while physicists often call it the linked cluster expansion and invoke it using colorful phrases like “connected vacuum bubbles exponentiate.” A basic example is the following: let be the number of simple graphs with vertex set let be the number of connected simply graphs with vertex set and form the generating functions

Then and the sequences and are related as in the Exponential Formula.

Now we return to Problem 1 above, which is to compute the coefficients in the expansion

We do this using the Exponential Formula: we have

where

The Exponential Formula now tells us that the coefficients we seek are given by

Thus, we have solved Problem 1: we see that

with the number of permutations of consisting of cycles, each of length at least

**Exercise 4**: Do the same computation instead using the Compositional Formula with