Analytic Combinatorics (book)

Last updated

Analytic Combinatorics is a book on the mathematics of combinatorial enumeration, using generating functions and complex analysis 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 in 2009. It won the Leroy P. Steele Prize in 2019.

Contents

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 generating functions or exponential generating functions of the classes, [1] [2] in some cases using tools such as the Lagrange inversion theorem as part of the reinterpretation process. [2] The chapters in this part divide the material into the enumeration of unlabeled objects, the enumeration of labeled objects, and multivariate generating functions. [2] [3]

The five chapters of the second part of the book, roughly half of the text [3] and "the heart of the book", [1] concern the application of tools from complex analysis to the generating function, in order to understand the asymptotics of the numbers of objects in a combinatorial class. [3] In particular, for sufficiently well-behaved generating functions, Cauchy's integral formula can be used to recover the power series 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. [1] After an introductory chapter and a chapter giving examples of the possible behaviors of rational functions and meromorphic functions, 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. [1] [3]

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. [3]

The combinatorial structures that are investigated throughout the book range widely over sequences, formal languages, integer partitions and compositions, permutations, graphs and paths in graphs, and lattice paths. With these topics, the analysis in the book connects to applications in other areas including abstract algebra, number theory, and the analysis of algorithms. [2] [4]

Audience and reception

Analytic Combinatorics is not primarily a textbook; for instance, it has no exercises. [4] Nevertheless, it can be used as the textbook for an upper-level undergraduate elective, [5] graduate course, [4] or seminar, [3] although reviewer Miklós Bóna writes that some selection is needed, as it "has enough material for three or more semesters". [2] It can also be a reference for researchers in this subject. [3]

Reviewer Toufik Mansour calls it not only "a comprehensive theoretical treatment" but "an interesting read". [3] 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". [4]

Analytic Combinatorics won the Leroy P. Steele Prize for Mathematical Exposition of the American Mathematical Society 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". [5] Although the application of analytic methods in combinatorics goes back at least to the work of G. H. Hardy and Srinivasa Ramanujan on the partition function, [1] 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. [1] [5] Similarly, Bóna concludes, "Analytic Combinatorics is now defined. The authors wrote the book on it." [2]

Related Research Articles

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science.

<span class="mw-page-title-main">Discrete mathematics</span> Study of discrete mathematical structures

Discrete mathematics is the study of mathematical structures that can be considered "discrete" rather than "continuous". Objects studied in discrete mathematics include integers, graphs, and statements in logic. By contrast, discrete mathematics excludes topics in "continuous mathematics" such as real numbers, calculus or Euclidean geometry. Discrete objects can often be enumerated by integers; more formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics".

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

Algebraic enumeration is a subfield of enumeration that deals with finding exact formulas for the number of combinatorial objects of a given type, rather than estimating this number asymptotically. Methods of finding these formulas include generating functions and the solution of recurrence relations.

<span class="mw-page-title-main">Robert Sedgewick (computer scientist)</span> American computer scientist

Robert Sedgewick is an American computer scientist. He is the founding chair and the William O. Baker Professor in Computer Science at Princeton University and was a member of the board of directors of Adobe Systems (1990–2016). He previously served on the faculty at Brown University and has held visiting research positions at Xerox PARC, Institute for Defense Analyses, and INRIA. His research expertise is in algorithm science, data structures, and analytic combinatorics. He is also active in developing the college curriculum in computer science and in harnessing technology to make that curriculum available to anyone seeking the opportunity to learn from it.

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

Analytic or analytical may refer to:

<span class="mw-page-title-main">Philippe Flajolet</span> French computer scientist

Philippe Flajolet was a French computer scientist.

In combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet and is detailed in Part A of his book with Robert Sedgewick, Analytic Combinatorics, while the rest of the book explains how to use complex analysis in order to get asymptotic and probabilistic results on the corresponding generating functions.

In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size.

<span class="mw-page-title-main">Richard P. Stanley</span> American mathematician

Richard Peter Stanley is an Emeritus Professor of Mathematics at the Massachusetts Institute of Technology, in Cambridge, Massachusetts. From 2000 to 2010, he was the Norman Levinson Professor of Applied Mathematics. He received his Ph.D. at Harvard University in 1971 under the supervision of Gian-Carlo Rota. He is an expert in the field of combinatorics and its applications to other mathematical disciplines.

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 infinite collection of finite sets Si indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.

The mathematical field of combinatorics was studied to varying degrees in numerous ancient societies. Its study in Europe dates to the work of Leonardo Fibonacci in the 13th century AD, which introduced Arabian and Indian ideas to the continent. It has continued to be studied in the modern era.

Mathematics is a broad subject that is commonly divided in many areas that may be defined by their objects of study, by the used methods, or by both. For example, analytic number theory is a subarea of number theory devoted to the use of methods of analysis for the study of natural numbers.

<span class="mw-page-title-main">Miklós Bóna</span> Hungarian-born American mathematician

Miklós Bóna is an American mathematician of Hungarian origin.

<span class="mw-page-title-main">Mireille Bousquet-Mélou</span> French mathematician

Mireille Bousquet-Mélou is a French mathematician who specializes in enumerative combinatorics and who works as a senior researcher for the Centre national de la recherche scientifique (CNRS) at the computer science department (LaBRI) of the University of Bordeaux.

Silvia Heubach is a German-American mathematician specializing in enumerative combinatorics, combinatorial game theory, and bioinformatics. She is a professor of mathematics at California State University, Los Angeles.

The Philippe Flajolet Lecture Prize is awarded to for contributions to analytic combinatorics and analysis of algorithms, in the fields of theoretical computer science. This prize is named in memory of Philippe Flajolet.

AofA, the International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms is an academic meeting that has been held regularly since 1993 in the field of computer science, focusing on mathematical methods from analytic combinatorics and probability for the study of properties of algorithms and large combinatorial structures. In early years, different formal names were used, but the meeting and associated community of researchers has always been known as AofA.

Analytic combinatorics uses techniques from complex analysis to find asymptotic estimates for the coefficients of generating functions.

References

  1. 1 2 3 4 5 6 Pemantle, Robin (September 2010), "Review of Analytic Combinatorics", SIAM Review , 52 (3): 572–576, JSTOR   20780175
  2. 1 2 3 4 5 6 Bóna, Miklós (June 2010), "Review of Analytic Combinatorics" (PDF), ACM SIGACT News , 41 (2): 11, doi:10.1145/1814370.1814373, S2CID   16443540
  3. 1 2 3 4 5 6 7 8 Mansour, Toufik, "Review of Analytic Combinatorics", zbMATH , Zbl   1165.05001
  4. 1 2 3 4 Hanusa, Christopher (July 2009), "Review of Analytic Combinatorics", MAA Reviews, Mathematical Association of America
  5. 1 2 3 "2019 Leroy P. Steele Prizes" (PDF), Notices of the American Mathematical Society , 66 (4): 594–598, April 2019
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.