''Analytic Combinatorics'' is a book on the mathematics of

combinatorial enumeration Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an inf ...

, using

generating function In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...

s and

complex analysis Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates functions of complex numbers. It is helpful in many branches of mathematics, including algebraic ...

to understand the growth rates of the numbers of combinatorial objects. It was written by Philippe Flajolet and Robert Sedgewick, and published by the

Cambridge University Press Cambridge University Press was the university press of the University of Cambridge. Granted a letters patent by King Henry VIII in 1534, it was the oldest university press in the world. Cambridge University Press merged with Cambridge Assessme ...

in 2009. It won the Leroy P. Steele Prize in 2019.

Topics

The main part of the book is organized into three parts. The first part, covering three chapters and roughly the first quarter of the book, concerns the symbolic method in combinatorics, in which classes of combinatorial objects are associated with formulas that describe their structures, and then those formulas are reinterpreted to produce the

s or exponential generating functions of the classes, in some cases using tools such as the Lagrange inversion theorem as part of the reinterpretation process. The chapters in this part divide the material into the enumeration of unlabeled objects, the enumeration of labeled objects, and multivariate generating functions. The five chapters of the second part of the book, roughly half of the text and "the heart of the book", concern the application of tools from complex analysis to the generating function, in order to understand the

asymptotics In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior. As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as bec ...

of the numbers of objects in a combinatorial class. In particular, for sufficiently well-behaved generating functions,

Cauchy's integral formula In mathematics, Cauchy's integral formula, named after Augustin-Louis Cauchy, is a central statement in complex analysis. It expresses the fact that a holomorphic function defined on a disk is completely determined by its values on the boundary o ...

can be used to recover the

power series In mathematics, a power series (in one variable) is an infinite series of the form \sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots where ''a_n'' represents the coefficient of the ''n''th term and ''c'' is a co ...

coefficients (the real object of study) from the generating function, and knowledge of the singularities of the function can be used to derive accurate estimates of the resulting integrals. After an introductory chapter and a chapter giving examples of the possible behaviors of

rational function In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be ...

s and

meromorphic function In the mathematical field of complex analysis, a meromorphic function on an open subset ''D'' of the complex plane is a function that is holomorphic on all of ''D'' ''except'' for a set of isolated points, which are ''poles'' of the function. ...

s, the remaining chapters of this part discuss the way the singularities of a function can be used to analyze the asymptotic behavior of its power series, apply this method to a large number of combinatorial examples, and study the saddle-point method of contour integration for handling some trickier examples. The final part investigates the behavior of random combinatorial structures, rather than the total number of structures, using the same toolbox. Beyond expected values for combinatorial quantities of interest, it also studies limit theorems and large deviations theory for these quantities. Three appendices provide background on combinatorics and asymptotics, in complex analysis, and in probability theory. The combinatorial structures that are investigated throughout the book range widely over

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...

formal language In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet". The alphabet of a formal language consists of symbols that concatenate into strings (also c ...

integer partition In number theory and combinatorics, a partition of a non-negative integer , also called an integer partition, is a way of writing as a summation, sum of positive integers. Two sums that differ only in the order of their summands are considered ...

s and compositions,

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

s, graphs and paths in graphs, and

lattice path In combinatorics, a lattice path in the -dimensional integer lattice of length with steps in the Set (mathematics), set , is a sequence of Vector (mathematics and physics), vectors such that each consecutive difference v_i - v_ lies in . A l ...

s. With these topics, the analysis in the book connects to applications in other areas including

abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures, which are set (mathematics), sets with specific operation (mathematics), operations acting on their elements. Algebraic structur ...

number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

, and the

analysis of algorithms In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...

Audience and reception

''Analytic Combinatorics'' is not primarily a textbook; for instance, it has no exercises. Nevertheless, it can be used as the textbook for an upper-level undergraduate elective, graduate course, or seminar, although reviewer Miklós Bóna writes that some selection is needed, as it "has enough material for three or more semesters". It can also be a reference for researchers in this subject. Reviewer Toufik Mansour calls it not only "a comprehensive theoretical treatment" but "an interesting read". Reviewer Christopher Hanusa writes that "the writing style is inviting, the subject material is contemporary and riveting", and he recommends the book to anyone "learning or working in combinatorics". ''Analytic Combinatorics'' won the Leroy P. Steele Prize for Mathematical Exposition of the

American Mathematical Society The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...

in 2019 (posthumously for Flajolet). The award citation called the book "an authoritative and highly accessible compendium of its subject, which demonstrates the deep interface between combinatorial mathematics and classical analysis". Although the application of analytic methods in combinatorics goes back at least to the work of

G. H. Hardy Godfrey Harold Hardy (7 February 1877 – 1 December 1947) was an English mathematician, known for his achievements in number theory and mathematical analysis. In biology, he is known for the Hardy–Weinberg principle, a basic principle of pop ...

and

Srinivasa Ramanujan Srinivasa Ramanujan Aiyangar (22 December 188726 April 1920) was an Indian mathematician. Often regarded as one of the greatest mathematicians of all time, though he had almost no formal training in pure mathematics, he made substantial con ...

on the partition function, the citation also quoted a review by Robin Pemantle stating that "This is one of those books that marks the emergence of a subfield," the subfield of analytic combinatorics. Similarly, Bóna concludes, "Analytic Combinatorics is now defined. The authors wrote the book on it."

References

{{reflist, refs= {{citation , last = Bóna , first = Miklós , date = June 2010 , doi = 10.1145/1814370.1814373 , issue = 2 , journal =

ACM SIGACT News ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer. Publi ...

, page = 11 , title = Review of ''Analytic Combinatorics'' , url = http://www.cs.umd.edu/~gasarch/BLOGPAPERS/flaj.pdf , volume = 41, s2cid = 16443540 {{citation , last = Hanusa , first = Christopher , date = July 2009 , journal = MAA Reviews , publisher =

Mathematical Association of America The Mathematical Association of America (MAA) is a professional society that focuses on mathematics accessible at the undergraduate level. Members include university A university () is an educational institution, institution of tertiary edu ...

, title = Review of ''Analytic Combinatorics'' , url = https://www.maa.org/press/maa-reviews/analytic-combinatorics {{citation , last = Mansour , first = Toufik , journal =

zbMATH zbMATH Open, formerly Zentralblatt MATH, is a major reviewing service providing reviews and abstracts for articles in pure and applied mathematics, produced by the Berlin office of FIZ Karlsruhe – Leibniz Institute for Information Infrastru ...

, title = Review of ''Analytic Combinatorics'' , zbl = 1165.05001 {{citation , last = Pemantle , first = Robin , date = September 2010 , issue = 3 , journal =

SIAM Review Society for Industrial and Applied Mathematics (SIAM) is a professional society dedicated to applied mathematics, computational science, and data science through research, publications, and community. SIAM is the world's largest scientific socie ...

, jstor = 20780175 , pages = 572–576 , title = Review of ''Analytic Combinatorics'' , volume = 52 {{citation , date = April 2019 , issue = 4 , journal =

Notices of the American Mathematical Society ''Notices of the American Mathematical Society'' is the membership journal of the American Mathematical Society (AMS), published monthly except for the combined June/July issue. The first volume was published in 1953. Each issue of the magazine ...

, pages = 594–598 , title = 2019 Leroy P. Steele Prizes , url = https://www.ams.org/journals/notices/201904/rnoti-p594.pdf , volume = 66

External links

Analytic Combinatorics
author web site, including a full-text downloadable copy of the book Enumerative combinatorics Mathematics books 2009 non-fiction books Cambridge University Press books