×

Analytic combinatorics. (English) Zbl 1165.05001

Cambridge: Cambridge University Press (ISBN 978-0-521-89806-5/hbk). xiii, 810 p. (2009).
Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick provides a comprehensive exposition of useful tools for studying the enumeration and asymptotic behavior of combinatorial configurations, with a focus on generating functions. The book begins with an enumerative description of combinatorial structures by means of generating functions. Then, generating functions are interpreted as mappings of the complex plane into itself to determine the asymptotic behavior of the counting sequences. These two methods are applied to a large number of problems and combinatorial structures, for example, compositions, graphs, mappings, partitions, permutations, planar configurations, and words. The combinatorial structures and analytic tools presented are widely applicable and have been selected from a wide variety of research papers by the authors. While there are many books on combinatorics, this book focuses on much needed methods for asymptotic analysis in addition to enumeration.
The book consists of four parts: (A) Symbolic methods (pp. 13–220), (B) Complex asymptotics (pp.221–608), (C) Random structures (pp. 609–718), and (D) Appendices (pp. 719–778).
In Part A, the authors develop the symbolic approach to combinatorial enumeration problems. It contains a unified algebraic theory dedicated to setting up functional relations between counting generating functions. A collection of general theorems provides a systematic translation between combinatorial descriptions and operations on generating functions. Part A contains three chapters: Chapter I deals with unlabeled objects, Chapter II deals with labeled objects, and Chapter III treats multivariate generating functions, which are suitable for the study of combinatorial structures according to several parameters.
Part B focuses on determining the asymptotic behavior of the coefficients of generating functions. General theorems for the asymptotic forms of coefficients of different types of generating functions are given. This part contains five chapters: Chapter IV gives an introduction to analytic methods from complex analysis. Chapter V presents applications and examples of the asymptotic behavior of the coefficients of rational and meromorphic generating functions. In Chapter VI, the authors develop a general singularity theory that covers a wide variety of singularity types, which is followed by 100 pages of applications in Chapter VII. Chapter VIII treats the saddle-point method and gives several combinatorial examples.
In Part C, the authors investigate random combinatorial structures. Topics range from discrete and continuous limit laws, in particular, Gaussian limit laws, to local limit laws, large deviations, and multivariate limit laws. In the process of developing these limit laws, many interesting and important examples of classical combinatorics are treated.
Part D contains three appendices: Appendix A presents some elementary facts of combinatorics and asymptotic analysis. Appendix B gives the necessary background in complex analysis, including analytic functions, the Gamma function, the implicit function theorem, and Mellin transform. Appendix C presents basic notions of probability theory that are useful in analytic combinatorics.
Analytic Combinatorics not only provides a comprehensive theoretical treatment of the topics described above, but also makes for an interesting read: there are thousands of examples from both combinatorics and neighboring areas of science that are often accompanied by beautiful illustrations. It is a self-contained resource and the very general singularity theory developed in it can be applied to many problems, old and new. Analytic Combinatorics can also be used as a text for several courses, for example, Chapters I-III present an introduction to the formal side of combinatorial enumeration. Chapters IV-VIII can be used for a seminar course in either pure or applied mathematics with a focus on the connection between complex analysis, singularity analysis, asymptotics, and (counting) generating functions from combinatorics and other branches of science. This text is a resource that should be on the shelves of everybody who studies asymptotic aspects of enumerative combinatorics and will surely become “the bible” on this topic.

MSC:

05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05A15 Exact enumeration problems, generating functions
05A16 Asymptotic enumeration
60C05 Combinatorial probability
60E10 Characteristic functions; other transforms
PDF BibTeX XML Cite

Online Encyclopedia of Integer Sequences:

Expansion of Product_{m >= 1} (1 + x^m); number of partitions of n into distinct parts; number of partitions of n into odd parts.
The positive integers. Also called the natural numbers, the whole numbers or the counting numbers, but these terms are ambiguous.
a(n) is the number of partitions of n (the partition numbers).
Number of trees with n unlabeled nodes.
Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point).
Number of graphs on n unlabeled nodes.
Euler or up/down numbers: e.g.f. sec(x) + tan(x). Also for n >= 2, half the number of alternating permutations on n letters (A001250).
Tangent (or ”Zag”) numbers: e.g.f. tan(x), also (up to signs) e.g.f. tanh(x).
Number of planar partitions (or plane partitions) of n.
Expansion of e.g.f. exp(x*exp(x)).
a(n) = n*a(n-1) + (n-1)*a(n-2), a(0) = 1, a(1) = 1.
Number of ”sets of lists”: number of partitions of {1,...,n} into any number of lists, where a list means an ordered subset.
Euler (or secant or ”Zig”) numbers: e.g.f. (even powers only) sec(x) = 1/cos(x).
Total number of ordered k-tuples (k=0..n) of distinct elements from an n-element set: a(n) = Sum_{k=0..n} n!/k!.
Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; or number of ordered partitions of [n].
Narayana’s cows sequence: a(0) = a(1) = a(2) = 1; thereafter a(n) = a(n-1) + a(n-3).
Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.
Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.
Number of connected labeled graphs with n nodes.
Triangle of Narayana numbers T(n,k) = C(n-1,k-1)*C(n,k-1)/k with 1 <= k <= n, read by rows. Also called the Catalan triangle.
a(n) = binomial(n, floor(n/2)).
a(n) = binomial(3*n,n)/(2*n+1) (enumerates ternary trees and also noncrossing trees).
Number of forests of trees on n labeled nodes.
Hertzsprung’s problem: ways to arrange n non-attacking kings on an n X n board, with 1 in each row and column. Also number of permutations of length n without rising or falling successions.
Number of partial permutations of an n-set; number of n X n binary matrices with at most one 1 in each row and column.
Number of self-avoiding polygons of length 2n on square lattice (not allowing rotations).
Number of connected permutations of [1..n] (those not fixing [1..j] for 0 < j < n). Also called indecomposable permutations, or irreducible permutations.
Number of unlabeled series-parallel posets (i.e., generated by unions and sums) with n nodes.
Expansion of e.g.f. log(1/(1+log(1-x))).
Number of fountains of n coins.
Closed meandric numbers (or meanders): number of ways a loop can cross a road 2n times.
Number of directed animals of size n (or directed n-ominoes in standard position).
E.g.f. is the logarithmic derivative of e.g.f. for Pell numbers [1, 0, 1, 2, 5, ...].
Number of connected graphs on n labeled nodes on a circle with straight-line edges that don’t cross.
Number of factorizations of permutations of n letters into ordered cycles.
Triangular numbers repeated.
Number of necklaces of sets of beads containing a total of n beads.
Number of 2n-step 2-dimensional closed self-avoiding paths on square lattice.
Decimal expansion of 2*Pi/3.
Expansion of 1/((1-x)*(1-x^3)*(1-x^7)).
Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n.
Number of monomer-dimer tilings of n X n chessboard.
Number of labeled 3-constrained functional graphs.
Number of connected labeled graphs with n edges and n nodes.
Array of numbers related to certain generalized Catalan sequences.
Number of spanning trees in K_{n}-e, the complete graph on n nodes minus an edge (n > 1).
Number of different hierarchical orderings that can be formed from n labeled elements: these are divided into groups and the elements in each group are then arranged in a ”preferential arrangement” or ”weak order” as in A000670.
Number of sets of sets of lists.
Analog of A054474 for walks on a 3-dimensional grid.
Array T(m,n) read by antidiagonals: number of domino tilings (or dimer tilings) of the m X n grid (or m X n rectangle), for m>=1, n>=1.
LAH transform of squares.
Array of coefficients of polynomials related to integer powers of the generating function of Catalan numbers A000108.
Triangle read by rows: T(n,k) is the number of (marked) circular binary words of length n having k occurrences of 00 (0 <= k <= n).
Number of ordered pairs of permutations generating a transitive group.
Define an array by d(m, 0) = 1, d(m, 1) = m; d(m, k) = (m - k + 1) d(m+1, k-1) - (k-1) (m+1) d(m+2, k-2). Sequence gives d(0,2n).
a(n) is the number of functions f:X->X, where |X| = n, such that for every x in X, f(f(x)) != x (i.e., the square of the function has no fixed points; note this implies that the function has no fixed points).
Triangle read by rows: T(n,k) is the number of ordered trees with n edges and path length k; 0 <= k <= n(n+1)/2.
Number of compositions of n with no part greater than 3 such that no two adjacent parts are equal.
Expansion of 1/((1-x)*(1-x^2-x^4)) + x/(1-3*x^3).
Triangle read by rows: T(n,k) = 1 + floor(n!/2^((k - n/2)^2 + 1)).
Irregular triangle read by rows: first row is 1, n-th row (n > 0) consists of the coefficients in the expansion of H(x;n)*(x + 1)^(n - 1)/2^floor(n/2), where H(x;n) is the Hermite polynomial of order n.
Coefficients of partition Hermite-Eulerian polynomials: p(x,n)= If[n == 0, 1, HermiteH[n, x]*Sum[Eulerian[n-1, k-1]*x^(k - 1), {k, 1, n}]/2^Floor[n/2]]
Coefficients of partition Hermite-MacMahon polynomials: p(x,n)= If[n == 0, 1, HermiteH[n, x]*Sum[MacMahon[n-1, k-1]*x^(k - 1), {k, 1, n}]/2^Floor[n/2]]
Decimal expansion of a constant appearing in the solution of Polya’s 2D drunkard problem.
The number of ways of putting n labeled items into k labeled boxes so that each box receives at least 2 objects.
E.g.f. satisfies: A(x) = x-1 + cosh(A(x)).
Triangular array read by rows. T(n,k) is the number of rooted labeled trees on n nodes such that the root node has degree k. n>=2, 1<=k<=n-1.
Triangular array read by rows. T(n,k) is the number of partial permutations (injective partial functions) of {1,2,...,n} that have exactly k elements in a cycle. The k elements are not necessarily in the same cycle. A fixed point is considered to be in a cycle.
The sum of the degree of each root node over all rooted labeled trees on n nodes.
Triangular array read by rows. T(n,k) is the number of compositions of the integer k into at most n summands, each of which is at most n, n >= 0, k >= 0.
Triangular array read by rows: T(n,k) is the number of set partitions of {1,2,...,n} that have exactly k distinct block sizes.
Expansion of (1 + sqrt( (1 + 2*x) / (1 - 2*x))) / 2 in powers of x.
The total number of components (cycles) in all alignments.
The total number of words in all length n finite languages on an alphabet of two letters.
Triangular array read by rows: T(n,k) is the number of partial permutations of {1,2,...,n} that have exactly k cycles, 0<=k<=n.
Triangular array read by rows, T(n,k) = number of partial functions on {1,2,...,n} with exactly k cycles.
Triangular array read by rows: T(n,k) is the number of compositions of n that have exactly k 3’s; n>=0, 0<=k<=floor(n/3).
Number of rooted factorizations of n-permutations into ordered cycles.
Triangular array read by rows: T(n,k) is the number of n-permutations that have exactly k distinct cycle lengths.
Number of ordered triples (a,b,c) of elements of the symmetric group S_n such that the triple a,b,c generates a transitive group.
Number of set partitions of {1,2,...,n} such that the size of the smallest block is unique and it contains the element 1.
Triangular array read by rows. T(n,k) is the number of square lattice walks that start and end at the origin after 2n steps having k primitive loops; n>=1, 1<=k<=n.
Number of binary sequences of length n that contain at least one contiguous subsequence 011.
Number of structures of size n in class A = o x (o + MSET(A)) where o is a neutral structure of size 1.
Triangular array read by rows: T(n,k) is the number of weakly unimodal partitions of n in which the greatest part occurs exactly k times, n>=1, 1<=k<=n.
Decimal expansion of Integral_{t=0..Pi/2} sqrt(tan(t)) dt.
E.g.f.: Log( Sum_{n>=0} (n+1)^(2*n) * x^n/n! ).
Decimal expansion of 1/exp(exp(1)-1).
Number of integer partitions of n whose Durfee square has sides of even size.
Triangular array read by rows: T(n,k) is the number of simple labeled graphs on n vertices, n>=1, with exactly k connected components, 1<=k<=n, such that the vertices labeled with 1,2,...,k are all in different components.
Number of simple labeled graphs G on n vertices such that for each k in {1,2,...,n}, G has exactly k connected components and the vertices labeled with {1,2,...,k} are all in different components.
Nearest integer to 2*n!*(2/Pi)^(n+1).
Number of A’Campo forests of degree n and co-dimension 5.
Triangular array read by rows. T(n,k) is the number of rooted labeled trees on n nodes with exactly k vertices whose unique descendent is a leaf, n >= 1, 0 <= k <= floor((n-1)/2) + delta_{2,n}.
Rectangular array read by rows: T(n,k) is the number of words of length n on alphabet {0,1,2} that have exactly k records, n>=0, 0<=k<=3.
Triangle read by rows: T(n,k) is the number of unmarked circular binary words (necklaces) of length n having k occurrences of the pattern 00 (n >= 0 and 0 <= k <= n).
Array of sequences read by descending antidiagonals, row A(n) is Stieltjes generated from the sequence n, n+1, n+2, n+3, ....
Numerator of the sum of inverse products of parts in all strict partitions of n.
Triangular array read by rows: T(n,k) is the number of ordered pairs of n-permutations that generate a group with exactly k orbits, 0 <= k <= n, n >= 0.
Number of plane trees of total weight n of combinatorial class T=Z*U + Z*T^2/(1-T) with nodes Z of weight one and leaves U of weight three.
Number of functions f:[n]->[n] such that no k exists such that |f^(-1)(k)| = k.
Number of functions f:[n]->[n] such that there exists a k such that |f^(-1)(k)| = k.
Triangle read by rows: T(n,k) is the number of ordered pairs of n-permutations with exactly k common double descents, n>=0, 0<=k<=max{0,n-2}.
Triangle read by rows: T(n,k) is the number of ordered triples of n-permutations with exactly k common descents, n>=0, 0<=k<=max(0,n-1).
Triangular array read by rows. T(n,k) is the number of length n words on alphabet {0,1} with k maximal runs of 0’s having length 2 or more, n>=0, 0<=k<=nearest integer to n/3.
a(n) is the number of chains from {} to a top element in the poset of even sized subsets of {1,2,...,n} ordered by inclusion.
Irregular triangular array read by rows. T(n,k) is the number of rooted labeled trees on n nodes with path length exactly k, n>=1, 0<=k<=C(n,2).
Triangular array read by rows. T(n,k) is the number of unlabeled binary trees with n internal nodes and exactly k distinguished external nodes (leaves) for 0 <= k <= n+1 and n >= 0.
Triangular array read by rows. T(n,k) is the number of closed walks of length 2n along the edges of a cube based at vertex v that return to v exactly k times, n>=0, 0<=k<=n.
Rectangular array read by antidiagonals. T(n,k) is the number of length k walks from {} to [n] in the digraph representation of the superset/subset relation on P([n]) the powerset of [n], n>=0, k>=0.
Decimal expansion of Pi*sqrt(2)*sqrt(2 + sqrt(2))/8.
Moments of the distribution of position of the first occurrence of pattern aa in a random ternary word.