CO 739: Analytic and Algorithmic Combinatorics
Stephen Melczer
Estimated study time: 55 minutes
Table of contents
These notes synthesize material from publicly available sources on analytic combinatorics, principally Philippe Flajolet and Robert Sedgewick’s Analytic Combinatorics (Cambridge University Press, 2009; freely available at algo.inria.fr/flajolet/Publications/book.pdf), Stephen Melczer’s An Invitation to Analytic Combinatorics in Several Variables (Springer, 2021; preprint on the author’s website), Herbert Wilf’s Generatingfunctionology (Academic Press, 2nd ed., 1994; freely available at www2.math.upenn.edu/~wilf/DownldGF.html), Robin Pemantle and Mark C. Wilson’s Analytic Combinatorics in Several Variables (Cambridge, 2013), Doron Zeilberger and Marko Petkovsek’s A=B (freely available), and supplementary public lecture notes by Igor Pak (UCLA) and Bruno Salvy (INRIA). All proofs and examples have been re-derived and re-phrased from these public sources.
Chapter 1: Generating Functions and the Symbolic Method
Analytic combinatorics is a discipline that uses complex analysis and generating functions to derive precise asymptotic information about combinatorial structures. Its central thesis, due to Flajolet and Sedgewick, is that one can pass directly from a combinatorial specification of a class of objects to an analytic expression for the generating function, and from the analytic properties of that generating function — particularly the location and nature of its singularities — to the asymptotic growth rate and limit law of the counting sequence. This chapter introduces the basic objects of the theory: combinatorial classes, generating functions, and the symbolic method.
1.1 Combinatorial Classes and Generating Functions
A combinatorial class is a (finite or denumerable) set \(\mathcal{A}\) together with a size function \(|\cdot|: \mathcal{A} \to \mathbb{Z}_{\ge 0}\) such that the set \(\mathcal{A}_n = \{\alpha \in \mathcal{A} : |\alpha| = n\}\) of objects of size \(n\) is finite for every \(n\). The counting sequence of \(\mathcal{A}\) is \(a_n = |\mathcal{A}_n|\).
The exponential generating function (EGF) is
\[ \hat{A}(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!} = \sum_{\alpha \in \mathcal{A}} \frac{z^{|\alpha|}}{|\alpha|!}. \]The choice between OGF and EGF depends on whether one is counting unlabelled structures (where atoms are interchangeable) or labelled structures (where atoms carry distinguishing labels \(1, 2, \ldots, n\)). For unlabelled classes — words, partitions, trees with anonymous nodes — the OGF is the natural object. For labelled classes — permutations, set partitions, labelled graphs — the EGF is forced upon us by the combinatorial product, in which two structures of sizes \(m\) and \(n\) can be combined in \(\binom{m+n}{m}\) ways by interleaving labels.
A formal power series ring \(\mathbb{C}[[z]]\) is the appropriate algebraic setting: one may add, multiply, differentiate, and (under mild hypotheses) compose power series without worrying about convergence. The leap to analysis comes when we ask whether \(A(z)\) converges in some disk \(|z| < \rho\); at that point the sequence \((a_n)\) is constrained by the Cauchy–Hadamard formula \(\rho = 1/\limsup_n a_n^{1/n}\), and the position of singularities on the boundary controls the growth.
1.2 The Symbolic Method for Unlabelled Classes
The symbolic method is a dictionary translating set-theoretic constructions on combinatorial classes into algebraic operations on generating functions. The basic atoms are the neutral class \(\mathcal{E}\) consisting of a single object of size \(0\), with OGF \(1\), and the atomic class \(\mathcal{Z}\) consisting of a single object of size \(1\), with OGF \(z\).
| Construction | OGF |
|---|---|
| Disjoint union: \(\mathcal{A} + \mathcal{B}\) | \(A(z) + B(z)\) |
| Product: \(\mathcal{A} \times \mathcal{B}\) | \(A(z) \cdot B(z)\) |
| Sequence: \(\mathrm{SEQ}(\mathcal{A})\), \(A(0)=0\) | \(\frac{1}{1-A(z)}\) |
| Multi-set: \(\mathrm{MSET}(\mathcal{A})\) | \(\prod_{\alpha} \frac{1}{1-z^{|\alpha|}} = \exp\!\left(\sum_{k \ge 1} \frac{A(z^k)}{k}\right)\) |
| Power-set: \(\mathrm{PSET}(\mathcal{A})\) | \(\exp\!\left(\sum_{k \ge 1} \frac{(-1)^{k-1} A(z^k)}{k}\right)\) |
| Cycle: \(\mathrm{CYC}(\mathcal{A})\) | \(\sum_{k \ge 1} \frac{\varphi(k)}{k} \log\frac{1}{1-A(z^k)}\) |
The product formula \(\sum_n c_n z^n = (\sum_m a_m z^m)(\sum_n b_n z^n)\) with \(c_n = \sum_{k=0}^n a_k b_{n-k}\) reflects the fact that an element of \(\mathcal{A} \times \mathcal{B}\) of size \(n\) is a pair \((\alpha, \beta)\) with \(|\alpha| + |\beta| = n\). The sequence formula iterates the product: \(\mathrm{SEQ}(\mathcal{A}) = \mathcal{E} + \mathcal{A} + \mathcal{A}^2 + \cdots\) gives \(1 + A + A^2 + \cdots = 1/(1-A)\). The Pólya-style multiset and powerset formulas account for unordered repetition with and without multiplicities; their derivation uses the cycle index of the symmetric group.
so \(c_n = 2^{n-1}\) for \(n \ge 1\). An (integer) partition is an unordered multiset of positive integers, so \(\mathcal{P} = \mathrm{MSET}(\mathrm{SEQ}_{\ge 1}(\mathcal{Z}))\), giving Euler’s formula
\[ P(z) = \prod_{k \ge 1} \frac{1}{1-z^k}. \]1.3 The Symbolic Method for Labelled Classes
For labelled classes, the combinatorial product \(\mathcal{A} \star \mathcal{B}\) is the labelled product: a pair \((\alpha, \beta)\) is replaced by all \(\binom{|\alpha|+|\beta|}{|\alpha|}\) order-consistent relabellings. The factor \(\binom{m+n}{m}\) is precisely what makes the EGF the right object: \(\frac{a_m}{m!} \cdot \frac{b_n}{n!} \cdot \binom{m+n}{m} = \frac{a_m b_n \binom{m+n}{m}}{m!\, n!}\) and summing over partitions of size gives \(\hat{A}(z) \hat{B}(z)\).
| Construction | EGF |
|---|---|
| Disjoint union | \(\hat{A}(z) + \hat{B}(z)\) |
| Labelled product | \(\hat{A}(z) \cdot \hat{B}(z)\) |
| Sequence \(\mathrm{SEQ}(\mathcal{A})\), \(\hat{A}(0)=0\) | \(\frac{1}{1-\hat{A}(z)}\) |
| Set \(\mathrm{SET}(\mathcal{A})\) | \(\exp(\hat{A}(z))\) |
| Cycle \(\mathrm{CYC}(\mathcal{A})\) | \(\log \frac{1}{1-\hat{A}(z)}\) |
The exponential formula \(\hat{A} \mapsto \exp(\hat{A})\) is the cornerstone of labelled enumeration: it says that the EGF of “sets of \(\mathcal{A}\)-objects” is the exponential of the EGF of \(\mathcal{A}\). Equivalently, the sequence \((a_n)\) of “connected structures” determines the sequence \((b_n)\) of “all structures” via \(\hat{B} = \exp(\hat{A})\); this is the exp–log inversion that pervades enumerative combinatorics.
1.4 Marking Parameters
If we wish to track an additional combinatorial parameter \(\chi\) (number of cycles, number of leaves, etc.), we introduce a marking variable \(u\) and consider the bivariate generating function \(A(z,u) = \sum_{\alpha} z^{|\alpha|} u^{\chi(\alpha)}\). The symbolic method extends naturally: a “marked atom” contributes \(zu\) instead of \(z\), and the constructions remain admissible. This bivariate framework is essential for limit-law theorems in Chapter 6.
Chapter 2: Singularity Analysis
Knowing a generating function does not, by itself, tell us how its coefficients grow. The bridge between formal-series identities and asymptotic enumeration is singularity analysis: the coefficient asymptotics of \(A(z)\) are controlled by the location, type, and multiplicity of the singularities of \(A\) on the boundary of its disk of convergence.
2.1 Radius of Convergence and the First Principle
The crude estimate \(a_n \asymp \rho^{-n}\) — more precisely, \(\rho^{-n}\) is the exponential growth rate \(\limsup a_n^{1/n}\) — is the first principle of coefficient asymptotics: exponential growth is dictated by the modulus of the nearest singularity to the origin. The subexponential factor (the polynomial or logarithmic correction \(a_n / \rho^{-n}\)) is governed by the nature of that singularity.
This theorem, fundamental for combinatorial GFs (whose coefficients are nonnegative integers), guarantees that the dominant singularity lives on the positive real axis — a substantial simplification.
2.2 Meromorphic Functions and Rational Asymptotics
The simplest case is a meromorphic GF whose dominant singularity is a pole. If \(A(z)\) is meromorphic in \(|z| < R\) with a single pole at \(z = \rho < R\) of order \(m\), then
\[ A(z) = \frac{c}{(1-z/\rho)^m} + (\text{lower-order singular terms}) + (\text{analytic part}), \]and the polar contribution dominates: \([z^n] (1-z/\rho)^{-m} = \binom{n+m-1}{m-1} \rho^{-n} \sim \frac{n^{m-1}}{(m-1)!} \rho^{-n}\).
where \(C_j(n)\) is a polynomial in \(n\) of degree \(m_j - 1\). When there is a unique dominant pole at \(z = \rho\) of order \(m\), \(a_n \sim \frac{c\, n^{m-1}}{(m-1)!\, \rho^{m}} \rho^{-n}\) for an explicit constant \(c\).
2.3 Standard Singular Expansions and the Transfer Theorem
For non-rational GFs — those with algebraic, logarithmic, or essential singularities — one needs a more powerful machinery. The Flajolet–Odlyzko transfer theorem asserts that a singular expansion of \(A(z)\) at its dominant singularity transfers to a coefficient asymptotic, provided \(A\) is analytic in a slightly larger region.
for some \(\phi \in (0, \pi/2)\) and \(\eta > 0\). A function is Delta-analytic at \(\rho\) if it is analytic in some such domain.
The Delta-domain is a disk of radius \(\rho+\eta\) with a small “Pacman bite” excised at the singularity \(\rho\); analyticity in this domain allows the Hankel-contour argument that drives the transfer theorem.
then
\[ [z^n] A(z) \sim \frac{n^{\alpha-1}}{\Gamma(\alpha)} \rho^{-n}. \]More generally, big-O and little-o error terms transfer term-by-term: if \(A(z) = \sum_j c_j (1-z/\rho)^{-\alpha_j} + O((1-z/\rho)^{-\beta})\) with \(\beta < \min \alpha_j\), then \([z^n]A = \sum_j c_j \frac{n^{\alpha_j - 1}}{\Gamma(\alpha_j)} \rho^{-n} + O(n^{\beta-1} \rho^{-n})\).
The basic singular scale \(\{(1-z/\rho)^{-\alpha} : \alpha \in \mathbb{R}\}\) together with its logarithmic enhancements covers virtually all combinatorial GFs: square roots (\(\alpha = -1/2\)) for trees, logarithms for harmonic-type counts, integer-power poles for rational GFs.
2.4 The Square-Root Singularity and Tree-Like Structures
By the transfer theorem with \(\alpha = -1/2\) and \(\rho = 1/4\),
\[ [z^n] T(z) \sim \frac{4^n}{2\sqrt{\pi n^3}}, \]recovering the classical Catalan asymptotic \(C_n \sim 4^n / \sqrt{\pi n^3}\).
This square-root singularity is universal: any “simple variety of trees” (\(\mathcal{T} = \mathcal{Z} \times \phi(\mathcal{T})\) for some “shape generator” \(\phi\)) has a generating function with a square-root singularity, leading to \(n^{-3/2}\) asymptotics. This is the \(n^{-3/2}\) phenomenon observed throughout tree enumeration.
2.5 Darboux’s Method
A precursor of singularity analysis is Darboux’s method, which derives coefficient asymptotics from the smoothness of the GF on its disk of convergence. Roughly, if \(A(z) = \sum c_j (1-z/\rho)^{\beta_j} + R(z)\) where \(R\) is sufficiently smooth on \(|z| = \rho\), then \([z^n] R = o(\rho^{-n} n^{-K})\) for any \(K\), and the singular terms dictate the asymptotics. Darboux’s method requires the singular part to have only finitely many singularities on the boundary circle, and it is generally subsumed by the Flajolet–Odlyzko transfer theorem when the latter applies. Darboux remains useful for problems with multiple singularities of equal modulus.
2.6 Multiple Singularities and Periodic Behavior
When \(A(z)\) has several singularities of the same minimal modulus, their contributions superimpose. If \(A(z)\) has dominant singularities \(\rho \omega_1, \ldots, \rho \omega_k\) (with \(|\omega_j| = 1\)) of the same nature, then
\[ a_n \sim \rho^{-n} n^{\alpha-1} \cdot \frac{1}{\Gamma(\alpha)} \sum_{j=1}^k c_j \omega_j^{-n}, \]producing periodic or quasi-periodic behavior in \(a_n\). A canonical example: \([z^n] 1/(1-z^2) = 1\) if \(n\) even, \(0\) if \(n\) odd — the alternation arising from the two poles \(z = \pm 1\).
Chapter 3: Saddle-Point Methods
When a generating function has no finite singularities — that is, when it is entire — singularity analysis cannot directly apply. The classical example is the EGF \(\exp(z) = \sum z^n/n!\). For such GFs, the relevant tool is the saddle-point method, a complex-analytic version of Laplace’s method that locates the steepest-descent contour for the Cauchy integral.
3.1 The Saddle-Point Heuristic
By Cauchy’s formula \(a_n = \frac{1}{2\pi i} \oint A(z) z^{-n-1} dz\). On a circle \(|z| = r\), the integrand has modulus \(|A(re^{i\theta})| r^{-n-1}\). For an entire function of moderate growth, this modulus is largest at \(\theta = 0\) (when \(A\) has positive Taylor coefficients) and behaves like \(\exp(h(r) - n \log r)\) for some real function \(h\). Optimising in \(r\) leads to the saddle-point equation
\[ r \frac{A'(r)}{A(r)} = n, \]determining a saddle radius \(r = r_n\). The Cauchy integral on the circle of radius \(r_n\) is then evaluated by quadratic Taylor expansion of the log-integrand.
3.2 Stirling’s Formula via Saddle Point
equivalently \(n! \sim n^n e^{-n} \sqrt{2\pi n}\) — Stirling’s formula.
3.3 Applications to Bell Numbers and Involutions
Equivalently \(B_n \sim n^{-1/2} (\lambda(n))^{n+1/2} e^{\lambda(n)-n-1}\) where \(\lambda(n) = n/W(n)\) — the famous Moser–Wyman asymptotic.
3.4 Large Powers and the Quasi-Powers Theorem
A bivariate version of the saddle-point method applies to large powers \(\phi(z)^n\), enabling local limit theorems. Specifically, if \(F(z, u) = \sum_{n,k} f_{n,k} z^n u^k\) and locally \(F(z,u) \approx (\text{analytic})\cdot \phi(u)^n\), then the distribution of \(k\) given \(n\) (suitably normalised) is asymptotically Gaussian — the Quasi-Powers theorem of Bender and Hwang. This is the principal tool for proving central limit theorems in combinatorics.
Chapter 4: Multivariate Analytic Combinatorics
Multivariate generating functions arise naturally when we mark several parameters simultaneously, count lattice paths constrained to wedges, or enumerate combinatorial structures decomposed into independent coordinates. The asymptotics of the diagonal coefficients \([z_1^{n_1} \cdots z_d^{n_d}] F(z_1, \ldots, z_d)\) along a ray \(n_j = \alpha_j n\) require the framework of Analytic Combinatorics in Several Variables (ACSV), developed by Pemantle, Wilson, Baryshnikov, and Melczer.
4.1 Multivariate Cauchy Integral and Critical Points
For an analytic function \(F(\mathbf{z}) = \sum_{\mathbf{n}} a_{\mathbf{n}} \mathbf{z}^{\mathbf{n}}\) on a polydisk, the multivariate Cauchy formula reads
\[ a_{\mathbf{n}} = \frac{1}{(2\pi i)^d} \oint_{T} \frac{F(\mathbf{z})}{\mathbf{z}^{\mathbf{n}+\mathbf{1}}} \, dz_1 \cdots dz_d, \]over a torus \(T = \{|z_j| = r_j\}\). The asymptotic analysis depends on the singular variety \(\mathcal{V} = \{\mathbf{z} : H(\mathbf{z}) = 0\}\) where \(F = G/H\) is meromorphic. Asymptotics along \(\mathbf{n} = n \mathbf{r} + O(1)\) are governed by the critical points of \(\mathcal{V}\) in direction \(\mathbf{r}\).
equivalently, the logarithmic gradient \((z_j \partial_j H)\) is proportional to \(\mathbf{r}\) at \(\mathbf{z}^*\).
The critical-point equations are the multivariate analogue of the saddle-point equation; they single out points on \(\mathcal{V}\) whose normal direction is “aimed” at the direction \(\mathbf{r}\) of asymptotic interest.
4.2 Smooth-Point Asymptotics
The term \((\mathbf{z}^*)^{-\mathbf{n}}\) carries the exponential growth — analogous to \(\rho^{-n}\) in one variable — while the \(n^{-(d-1)/2}\) factor reflects the codimension-1 saddle in \(d\)-dimensional integration. Minimality means \(\mathbf{z}^*\) lies on the boundary of the open polydisk of convergence; combinatorial conditions (positive coefficients, etc.) often guarantee this.
agreeing with the classical Stirling-based asymptotic.
4.3 Multiple Points and Cone Points
When \(\mathcal{V}\) is singular at the critical point — say two sheets cross transversely at \(\mathbf{z}^*\) — the asymptotics change form. Multiple points (transverse intersections of smooth strata of \(\mathcal{V}\)) lead to a different leading order, often without the \(n^{-(d-1)/2}\) factor. Cone points (where \(H\) vanishes to higher order) lead to integrals over Airy-type kernels and \(n^{-1/3}\) scaling. ACSV provides a complete classification: the local geometry of \(\mathcal{V}\) at the critical point determines the precise asymptotic regime.
4.4 The Morse-Theoretic Picture
The geometric heart of ACSV is a Morse-theoretic deformation argument. The torus of integration in the multivariate Cauchy integral is deformed across the singular variety \(\mathcal{V}\); each time it crosses a critical point, a “residue” contribution is picked up, mirroring the way classical residue calculus picks up poles in the one-variable case. The resulting decomposition expresses \(a_{\mathbf{n}}\) as a sum of integrals over residue forms localized at critical points, each of which is then estimated by a stationary-phase or saddle-point argument. This picture, due to Baryshnikov and Pemantle, places ACSV firmly within stratified Morse theory.
Chapter 5: Algorithmic Aspects and the Kernel Method
A defining feature of CO 739 is its emphasis on effective and algorithmic methods. Generating functions are not merely existence-proofs of asymptotics; they are computable objects, and powerful algorithms exist to manipulate them, derive their differential or recurrence relations, and extract their coefficient asymptotics rigorously.
5.1 D-finite and D-algebraic Functions
with \(p_j(z) \in \mathbb{Q}[z]\), \(p_r \ne 0\). Equivalently, the \(\mathbb{Q}(z)\)-vector space spanned by \(\{f, f', f'', \ldots\}\) is finite-dimensional.
D-finiteness is the algorithmic analogue of analyticity: a D-finite series is encoded by a finite ODE plus initial conditions, and all the standard manipulations have effective algorithms (implemented in Maple’s gfun and Mathematica).
The translation \(f \leftrightarrow (a_n)\) is bidirectional and constructive: from an ODE for \(f\), one extracts a recurrence for \(a_n\) by matching coefficients, and conversely.
5.2 The Kernel Method
The kernel method is an algebraic technique for solving functional equations of the form
\[ K(z, u) F(z, u) = G(z, u) + R(z) H(z, u) \]where \(F(z,u)\) is the unknown bivariate GF, \(K\) is the kernel, and \(R(z)\) encodes a “boundary” generating function. It was pioneered for lattice path enumeration: paths in a half-plane or quadrant can be encoded by step-by-step generating functions whose recursions satisfy precisely this form.
The kernel is \(K(z,u) = u - zu^2 - z\). The trick: substitute the root \(u_0(z) = (1 - \sqrt{1-4z^2})/(2z)\) of the kernel \(K(z, u_0) = 0\) into the equation; the left-hand side vanishes, leaving
\[ D(z, 0) = u_0(z)/z = \frac{1 - \sqrt{1-4z^2}}{2z^2}, \]whose coefficients (at even \(n\)) are the Catalan numbers — the classical count of Dyck paths.
determining \(R(z)\) (typically the unknown GF tracking a marginal statistic).
5.3 Quadrant Walks and the Obstinate Kernel Method
For walks in the quarter plane with a step set \(\mathcal{S} \subset \{-1,0,1\}^2 \setminus \{(0,0)\}\), the GF \(Q(z; x, y) = \sum_w z^{|w|} x^{i(w)} y^{j(w)}\) (over walks \(w\) with endpoint \((i(w), j(w))\)) satisfies
\[ K(z;x,y) Q(z;x,y) = xy - zF_1(x) - zF_2(y), \]where the kernel \(K(z;x,y) = xy - z\, xy \,\sum_{(i,j) \in \mathcal{S}} x^i y^j\) and \(F_1, F_2\) encode the \(y=0\) and \(x=0\) boundaries. Mishna and Bousquet-Mélou classified the 79 inherently distinct nontrivial small-step models. The group of the walk — generated by birational involutions that exchange \((x,y) \leftrightarrow (\bar{x}, y)\) and \((x,y) \leftrightarrow (x, \bar{y})\) on the kernel curve — controls solvability.
This dichotomy — D-finite if and only if finite group, modulo a small list of exceptions — is one of the most striking results in modern enumerative combinatorics, demonstrating how the algorithmic notion of D-finiteness aligns with intrinsic combinatorial-geometric structure.
5.4 Creative Telescoping
To evaluate or simplify sums involving binomial-coefficient or hypergeometric-like terms, the Wilf–Zeilberger (WZ) method of creative telescoping is a fully algorithmic engine.
Summing over \(k\) (telescoping the right-hand side) yields a P-recurrence for \(S(n) = \sum_k F(n,k)\).
The algorithm exhibits the polynomials \(a_j\) and the certificate \(G\) explicitly; the certificate provides a checkable proof of the resulting recurrence.
5.5 Effective Asymptotics and the Sage ACSV Package
Combining D-finiteness with singularity analysis allows fully effective coefficient-asymptotic algorithms. Given a D-finite GF \(f(z)\) by ODE and initial conditions, one computes (a) the singular points of the ODE (zeros of leading coefficient), (b) the local exponents at each singularity (indicial equation), and (c) the connection coefficients matching local solutions to the global one. This “rigorous numerical analytic continuation” (van der Hoeven, Mezzarobba) yields provably correct asymptotics with explicit error bounds. Melczer’s sage_acsv package implements the multivariate analogue: for a rational \(F = G/H\), it computes critical points, verifies minimality, and outputs the leading-order asymptotic with provable correctness in many cases.
Chapter 6: Limit Laws and Random Combinatorial Structures
Beyond first-order asymptotics of counting sequences, analytic combinatorics provides a fine-grained probabilistic description: it computes the limit distributions of natural parameters of a uniformly random combinatorial structure of size \(n\).
6.1 Bivariate Generating Functions and Marked Parameters
If \(F(z, u) = \sum_{n,k} f_{n,k} z^n u^k\) marks a parameter \(\chi\) on a class \(\mathcal{F}\), then the probability that \(\chi(\alpha) = k\) for \(\alpha\) uniform in \(\mathcal{F}_n\) is \(p_{n,k} = f_{n,k}/f_n\) where \(f_n = [z^n] F(z, 1)\). The probability generating function of \(\chi\) on \(\mathcal{F}_n\) is
\[ P_n(u) = \frac{[z^n] F(z, u)}{[z^n] F(z, 1)}. \]6.2 The Quasi-Powers Theorem
with rate of convergence \(O(\sigma_n^{-1} + \kappa_n^{-1})\).
The quasi-powers theorem is the workhorse for proving Gaussian limit laws in combinatorics: any bivariate GF whose dominant singularity moves analytically with the marking parameter \(u\) and whose dominant local behavior takes the quasi-powers form yields a Gaussian-distributed parameter.
6.3 Patterns and Profile of Trees
The size of various subtree statistics of random Catalan trees — number of leaves, number of nodes of out-degree \(k\), height profile — can be analyzed by bivariate GFs and the smooth-point theorem. The number of leaves in a random plane tree of size \(n\) is asymptotically Gaussian with mean \(\sim n/2\) and variance \(\sim n/8\). The height of such a tree, however, exhibits non-Gaussian behavior: it concentrates around \(\sqrt{\pi n}\) with Theta-distribution fluctuations, a phenomenon discovered by de Bruijn, Knuth, and Rice.
6.4 Lattice Paths and the Cycle Lemma
The cycle lemma converts cyclic-symmetry counting into linear counting and is a recurring tool in lattice-path enumeration, often complementing the kernel method for problems amenable to bijective treatment.
Chapter 7: Asymptotics of Combinatorial Sequences and Applications
This final chapter assembles the theory of the previous chapters into a unified workflow for asymptotic enumeration and surveys characteristic applications.
7.1 The Analytic Combinatorics Workflow
The asymptotic enumeration of a combinatorial class \(\mathcal{A}\) proceeds in five stages. First, one specifies \(\mathcal{A}\) as a combinatorial construction over atoms. Second, one applies the symbolic method to obtain a closed-form or implicit equation for \(A(z)\). Third, one performs an analytic study to locate the dominant singularity \(\rho\) and determine the type of singular behavior. Fourth, one transfers — applying singularity analysis (or the saddle-point method, in the entire-function case) to extract \([z^n] A(z)\). Finally, one refines: lower-order corrections, error terms, and bivariate (limit-law) information are computed as needed.
This pipeline is intentionally modular: each stage admits independent algorithmic improvement, and the framework gracefully accommodates parametric families, multivariate marking, and asymptotic uniformity.
7.2 Smirnov Words and Pattern Avoidance
The dominant pole at \(z = 1/(\sigma-1)\) gives \(s_n \sim \sigma (\sigma-1)^{n-1}\). More refined: the bivariate GF \(S(z, u)\) marking the number of distinct letters used yields a Gaussian limit by quasi-powers.
7.3 Random Maps and the Brownian Map
The enumeration of planar maps — connected planar graphs embedded in the sphere — was solved by Tutte (1962) using the kernel-style “quadratic method.” The number of rooted planar maps with \(n\) edges is
\[ M_n = \frac{2 \cdot 3^n (2n)!}{n!\, (n+2)!} \sim \frac{2}{\sqrt{\pi}} \cdot \frac{12^n}{n^{5/2}}, \]exhibiting the universal map-asymptotic with \(n^{-5/2}\). The Schaeffer bijection and Le Gall’s continuum scaling limit theorem identify the geometric profile of large random maps with the Brownian map, a random metric space.
7.4 Random Graphs at the Phase Transition
The random graph \(G(n, M)\) with \(M = (1+\mu n^{-1/3})n/2\) edges undergoes a phase transition near \(\mu = 0\) — the double-jump of Erdős and Rényi. Flajolet, Knuth, and Pittel used singularity analysis of multivariate GFs (with marking on the number of components and on excess) to derive precise asymptotic distributions of component sizes, the size of the giant component, and the number of “complex” components. The methods of multivariate analytic combinatorics fit naturally into this framework.
7.5 Closing Perspective
The unifying message of analytic combinatorics is that combinatorial structure, once captured in a generating function, surrenders its asymptotic and probabilistic secrets to the tools of complex analysis. The theory thus binds three threads — combinatorial specification, algebraic manipulation of formal series, and complex-analytic asymptotic estimation — into a single, broadly applicable methodology. With the recent extension to several variables (ACSV) and effective algorithmic refinements (D-finite algorithms, kernel-method classifications, certified asymptotics), analytic combinatorics has matured into both a rich theoretical framework and a practical computational discipline. For the working combinatorialist, it provides a near-universal recipe: specify the structure, encode it as a generating function, locate the singularities, and read off the asymptotic behavior — a recipe that has illuminated tree enumeration, lattice-path counting, random map theory, additive number theory, and far beyond.
