Analytic Combinatorics

Provides a unified treatment of analytic methods in combinatorics. Many examples are given that relate to words, integer compositions and partitions, paths and walks, graphs, mappings and allocations, lattice paths, permutations, trees, and planar maps.

**Tag(s):**
Mathematics

**Publication date**: 23 Oct 2006

**ISBN-10**:
n/a

**ISBN-13**:
n/a

**Paperback**:
745 pages

**Views**: 15,805

**Type**: N/A

**Publisher**:
n/a

**License**:
n/a

**Post time**: 20 Apr 2007 07:42:20

Analytic Combinatorics

Provides a unified treatment of analytic methods in combinatorics. Many examples are given that relate to words, integer compositions and partitions, paths and walks, graphs, mappings and allocations, lattice paths, permutations, trees, and planar maps.

From the Preface:

Analytic Combinatorics aims at predicting precisely the properties of large structured combinatorial configurations, through an approach based extensively on analytic methods. Generating functions are the central objects of the theory.

Analytic Combinatorics starts from an exact enumerative description of combinatorial structures by means of generating functions, which make their first appearance as purely formal algebraic objects. Next, generating functions are interpreted as analytic objects, that is, as mappings of the complex plane into itself. Singularities determine a function’s coefficients in asymptotic form and lead to precise estimates for counting sequences. This chain applies to a large number of problems of discrete mathematics relative to words, trees, permutations, graphs, and so on. A suitable adaptation of the methods also opens the way to the quantitative analysis of characteristic parameters of large random structures, via a perturbational approach.

This book is meant to be reader-friendly. Each major method is abundantly illustrated by means of concrete examples treated in detail -- there are scores of them, spanning froma fraction of a page to several pages -- offering a complete treatment of a specific problem. These are borrowed not only from combinatorics itself but also from neighbouring areas of science. With a view of addressing not only mathematicians of varied profiles but also scientists of other disciplines, Analytic Combinatorics is self contained, including ample appendices that recapitulate the necessary background in combinatorics and complex function theory. A rich set of short Notes -- there are more than 250 of them -- are inserted in the text and can provide exercises meant for self study or for students' practice, as well as introductions to the vast body of literature that is available. We have also made every effort to focus on core ideas rather than technical details, supposing a certain amount of mathematical maturity but only basic prerequisites on the part of our gentle readers. The book is also meant to be strongly problem-oriented, and indeed it can be regarded as amanual, or even a huge algorithm, guiding the reader to the solution of a very large variety of problems regarding discrete mathematical models of varied origins. In this spirit, many of our developments connect nicely with computer algebra and symbolic manipulation systems.

Courses can be (and indeed have been) based on the book in various ways. Chapters I–III on Symbolic Methods serve as a systematic yet accessible introduction to the formal side of combinatorial enumeration. As such it organizes transparently some of the rich material found in treatises like those of Bergeron-Labelle-Leroux, Comtet, Goulden-Jackson, and Stanley. Chapters IV–VIII relative to Complex Asymptotics provide a large set of concrete examples illustrating the power of classical complex analysis and of asymptotic analysis outside of their traditional range of applications. This material can thus be used in courses of either pure or applied mathematics, providing a wealth of nonclassical examples. In addition, the quiet but ubiquitous presence of symbolic manipulation systems provides a number of illustrations of the power of these systems while making it possible to test and concretely experiment with a great many combinatorial models. Symbolic systems allow for instance for fast random generation, close examination of non-asymptotic regimes, efficient experimentation with analytic expansions and singularities, and so on.

Analytic Combinatorics aims at predicting precisely the properties of large structured combinatorial configurations, through an approach based extensively on analytic methods. Generating functions are the central objects of the theory.

Analytic Combinatorics starts from an exact enumerative description of combinatorial structures by means of generating functions, which make their first appearance as purely formal algebraic objects. Next, generating functions are interpreted as analytic objects, that is, as mappings of the complex plane into itself. Singularities determine a function’s coefficients in asymptotic form and lead to precise estimates for counting sequences. This chain applies to a large number of problems of discrete mathematics relative to words, trees, permutations, graphs, and so on. A suitable adaptation of the methods also opens the way to the quantitative analysis of characteristic parameters of large random structures, via a perturbational approach.

This book is meant to be reader-friendly. Each major method is abundantly illustrated by means of concrete examples treated in detail -- there are scores of them, spanning froma fraction of a page to several pages -- offering a complete treatment of a specific problem. These are borrowed not only from combinatorics itself but also from neighbouring areas of science. With a view of addressing not only mathematicians of varied profiles but also scientists of other disciplines, Analytic Combinatorics is self contained, including ample appendices that recapitulate the necessary background in combinatorics and complex function theory. A rich set of short Notes -- there are more than 250 of them -- are inserted in the text and can provide exercises meant for self study or for students' practice, as well as introductions to the vast body of literature that is available. We have also made every effort to focus on core ideas rather than technical details, supposing a certain amount of mathematical maturity but only basic prerequisites on the part of our gentle readers. The book is also meant to be strongly problem-oriented, and indeed it can be regarded as amanual, or even a huge algorithm, guiding the reader to the solution of a very large variety of problems regarding discrete mathematical models of varied origins. In this spirit, many of our developments connect nicely with computer algebra and symbolic manipulation systems.

Courses can be (and indeed have been) based on the book in various ways. Chapters I–III on Symbolic Methods serve as a systematic yet accessible introduction to the formal side of combinatorial enumeration. As such it organizes transparently some of the rich material found in treatises like those of Bergeron-Labelle-Leroux, Comtet, Goulden-Jackson, and Stanley. Chapters IV–VIII relative to Complex Asymptotics provide a large set of concrete examples illustrating the power of classical complex analysis and of asymptotic analysis outside of their traditional range of applications. This material can thus be used in courses of either pure or applied mathematics, providing a wealth of nonclassical examples. In addition, the quiet but ubiquitous presence of symbolic manipulation systems provides a number of illustrations of the power of these systems while making it possible to test and concretely experiment with a great many combinatorial models. Symbolic systems allow for instance for fast random generation, close examination of non-asymptotic regimes, efficient experimentation with analytic expansions and singularities, and so on.

Tweet

About The Author(s)

No information is available for this author.

Robert Sedgewick is a William O. Baker Professor in the Department of Computer Science at Princeton University. He is also a member of the board of directors of Adobe Systems. Sedgewick completed his Ph.D. in 1975 under the supervision of Donald Knuth at Stanford. His research is in analysis of algorithms.

Book Categories

Computer Science
15
Introduction to Computer Science
33
Introduction to Computer Programming
52
Algorithms and Data Structures
24
Artificial Intelligence
24
Computer Vision
28
Machine Learning
6
Neural Networks
22
Game Development and Multimedia
25
Data Communication and Networks
5
Coding Theory
15
Computer Security
8
Information Security
35
Cryptography
3
Information Theory
17
Computer Organization and Architecture
22
Operating Systems
1
Image Processing
10
Parallel Computing
4
Concurrent Programming
19
Relational Database
3
Document-oriented Database
13
Data Mining
16
Big Data
17
Data Science
23
Digital Libraries
22
Compiler Design and Construction
25
Functional Programming
11
Logic Programming
26
Object Oriented Programming
21
Formal Methods
70
Software Engineering
3
Agile Software Development
7
Information Systems
5
Geographic Information System (GIS)

Mathematics
68
Mathematics
13
Algebra
28
Linear Algebra
3
Number Theory
8
Numerical Methods
2
Precalculus
10
Calculus
5
Category Theory
10
Proofs
19
Discrete Mathematics
24
Theory of Computation
14
Graph Theory
1
Complex Analysis
13
Probability
43
Statistics
7
Game Theory
5
Queueing Theory
13
Operations Research
16
Computer Aided Mathematics

Supporting Fields
19
Web Design and Development
1
Mobile App Design and Development
29
System Administration
2
Cloud Computing
9
Electric Circuits
6
Embedded System
26
Signal Processing
4
Network Science
3
Project Management

Operating System
Programming/Scripting
6
Ada
13
Assembly
34
C / C++
8
Common Lisp
2
Forth
36
Java
12
JavaScript
1
Lua
15
Microsoft .NET
1
Rexx
12
Perl
6
PHP
66
Python
12
R
1
Rebol
13
Ruby
2
Scheme
3
Tcl/Tk

Miscellaneous