5.   Analytic Combinatorics


This chapter introduces analytic combinatorics, a modern approach to the study of combinatorial structures of the sort that we encounter frequently in the analysis of algorithms. The approach is predicated on the idea that combinatorial structures are typically defined by simple formal rules that are the key to learning their properties. One eventual outgrowth of this observation is that a relatively small set of transfer theorems ultimately yields accurate approximations of the quantities that we seek. Figure 5.1 gives an general overview of the process. Generating functions are the central objects of study in analytic combinatorics. In the first place, we directly translate formal definitions of combinatorial objects into definitions of generating functions that enumerate objects or describe their properties. In the second place, we use classical mathematical analysis to extract estimates of generating function coefficients.


5.1 Formal Basis


5.2 Symbolic Method for Unlabelled Classes


5.3 Symbolic Method for Labelled Classes


5.4 Symbolic Method for Parameters


5.5 Generating Function Coefficient Asymptotics

Selected Exercises


5.1

How many bitstrings of length $N$ have no 000?


5.3

Let $\cal U$ be the set of binary trees with the size of a tree defined to be the total number of nodes (internal plus external), so that the generating function for its counting sequence is $U(z) = z + z^3 + 2 z^5 + 5z^7 + 14z^9 + \ldots\,\,$. Derive an explicit expression for $U(z)$.


5.7

Derive an EGF for the number of permutations whose cycles are all of odd length.

5.15

Find the average number of internal nodes in a binary tree of size $N$ with both children internal.

5.16

Find the average number of internal nodes in a binary tree of size $N$ with one child internal and one child external.


5.23

Show that the probability that all of the cycles are of odd length in a random permutation of length $N$ is $1/\sqrt{\pi N/2}$ (see Exercise 5.7).