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
2 Comments