Introduction

We start with an informal presentation of how to understand different sorts of generating functions in the context of analytic combinatorics and which techniques to apply to which functions. Little background knowledge of complex analysis is assumed.

Representing generating functions in the complex plane

We are used to seeing generating functions as formal objects. For example, unrestricted integer compositions have the below ordinary generating function and power series expansion.^[1]

${\displaystyle {\frac {1-z}{1-2z}}=1+z+2z^{2}+4z^{3}+8z^{4}+16z^{5}+\cdots }$

We can also see generating functions as "complex-analytic" functions: those whose input and output are complex numbers. A complex number has two components, a "real" and an "imaginary" part. Therefore, we can graph the above generating function as a three-dimensional landscape, the north-south and east-west plane measuring the real and imaginary parts of the input and the height of the graph measuring the magnitude of the output.

Functions with one pole singularity

Notice that there is a peak when the input has real part 0.5 and imaginary part 0. Actually, this peak should extend up to infinity but we are limited by our technology. This is because if we set ${\displaystyle z=1/2}$ then

${\displaystyle {\frac {1-{\frac {1}{2}}}{1-2{\frac {1}{2}}}}={\frac {1-{\frac {1}{2}}}{1-1}}={\frac {1-{\frac {1}{2}}}{0}}=\infty }$

Where such a peak occurs is called a pole singularity. Therefore, for our function, we have a pole singularity at 1/2.

We will see by the Cauchy-Hadamard theorem that, if we take the reciprocal of the singularity (i.e. 2), we can get upper and (with some caveats) lower bounds for our estimates of the coefficients. For any ${\displaystyle \epsilon >0}$ there are infinite ${\displaystyle n}$ such that ${\displaystyle (2-\epsilon )^{n}<|f_{n}|<(2+\epsilon )^{n}}$.

Comparing the upper and lower bounds and the actual value of ${\displaystyle f_{n}}$ for e = 0.01

n	${\displaystyle (2-\epsilon )^{n}}$	${\displaystyle f_{n}}$	${\displaystyle (2+\epsilon )^{n}}$
500	2.670165651072143E+149	1.636695303948071E+150	3.96304232182789E+151
750	1.379771935849753E+224	2.961193260766428E+225	2.49484210739009E+227
1000	7.129784604165516E+298	5.357543035931337E+300	1.5705704444599E+303

But, because our function has only one pole singularity, we can use an even better estimate for Meromorphic functions: ${\displaystyle 2^{n-1}}$ (which is in fact the actual value of ${\displaystyle f_{n}}$).

Other generating functions which have only one pole singularity include derangements and alignments.

s(n, k) is the unsigned Stirling number of first kind

Name	Surface graph	(Exponential) generating function	Cauchy-Hadamard upper-bound	Meromorphic estimate	Actual value
Derangements		${\displaystyle {\frac {e^{-z}}{1-z}}}$	${\displaystyle {\frac {1}{n!}}|d_{n}|<(1+\epsilon )^{n}}$	${\displaystyle n!e^{-1}}$	${\displaystyle n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$
Alignments		${\displaystyle {\frac {1}{1-\log {\frac {1}{1-z}}}}}$	${\displaystyle {\frac {1}{n!}}|a_{n}|<(1.582+\epsilon )^{n}}$	${\displaystyle {\frac {n!e^{-1}}{(1-e^{-1})^{n+1}}}}$	${\displaystyle \sum _{k=1}^{n}k!s(n,k)}$[2]

Functions with more than one pole singularity

Many generating functions have more than one pole singularity. Fortunately, the above analysis also applies if there is one pole closest to the origin and all other poles are further away.

For example, the Fibonacci numbers with the ordinary generating function ${\displaystyle {\frac {z}{1-z-z^{2}}}}$

This has two poles at ${\displaystyle {\frac {-1+{\sqrt {5}}}{2}}{\dot {=}}0.61803}$ and ${\displaystyle {\frac {-1-{\sqrt {5}}}{2}}{\dot {=}}-1.61803}$.^[3] The nearest to the origin is ${\displaystyle 0.61803}$.

This gives us a Cauchy-Hadamard upper-bound of roughly ${\displaystyle (1.61804+\epsilon )^{n}}$ and a meromorphic estimate of ${\displaystyle {\frac {1.61804^{n}}{\sqrt {5}}}}$.

It even works if there are an infinite number of pole singularities, such as in the case of surjections, with exponential generating function ${\displaystyle (2-e^{z})^{-1}}$.

This has poles at all points ${\displaystyle \log 2+2ik\pi }$, with ${\displaystyle k}$ one of ${\displaystyle \{\cdots ,-2,-1,0,1,2,\cdots \}}$.^[4] The nearest to the origin is ${\displaystyle \log 2{\dot {=}}0.69315}$.

This gives an upper-bound of ${\displaystyle {\frac {1}{n!}}|s_{n}|<\left({\frac {1}{\log 2}}+\epsilon \right)^{n}}$ and a meromorphic estimate of ${\displaystyle {\frac {n!}{2}}\left({\frac {1}{\log 2}}\right)^{n+1}}$.

Functions with multiple dominant pole singularities

Some generating functions have multiple poles equidistant to the origin.

For example, ${\displaystyle {\frac {1}{1-z^{2}}}}$ has two poles at ${\displaystyle 1}$ and ${\displaystyle -1}$.

Sadly, it is harder to work out estimates for these functions, as their coefficients have periodic behaviour. For example, the above function has expansion ${\displaystyle 1+z^{2}+z^{4}+z^{6}+\cdots }$.

We will see in Analytic_Combinatorics/Meromorphic_Functions_with_Multiple_Dominant_Singularities what it is possible to say about such functions.

Functions with different sorts of singularities

Generating functions involving logarithms and roots have singularities different from poles, meaning we cannot apply the meromorphic formula presented above.

These types of singularity, called branch points, only become apparent when we plot the output in terms not of its magnitude but of its argument, its angle from the real axis.

Take the generating function for 2-regular graphs ${\displaystyle {\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}}$.^[5]

There is a discontinuity or "jump" along the real axis from 1 to ${\displaystyle \infty }$.

We can still apply Cauchy-Hadamard (with radius of convergence 1 in our example) or more sophisticated techniques from Darboux, Tauber and singularity analysis to say that the coefficients are approximately ${\displaystyle {\frac {e^{-3/4}}{\sqrt {\pi n}}}}$.

Functions with singularities only at infinity

The generating function ${\displaystyle e^{z}}$ has no singularity for any complex number other than at infinity. It is an entire function.

Our strategy is derived from Cauchy's coefficient formula and involves the function ${\displaystyle {\frac {e^{z}}{z^{n+1}}}}$, drawing a circle on its surface and integrating around it.

There are two ways of estimating this integral:

1. Cauchy's inequality a simple formula giving us an upper-bound by integrating around the orange circle below, or
2. the Saddle-point method where we concentrate on the highest part of the circle (in red below).

Notes

References

• Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
• Sloane, N. J. A. (ed.). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.