Analytic combinatorics
![]() | This article needs attention from an expert in Mathematics. Please add a reason or a talk parameter to this template to explain the issue with the article.(January 2024) |
Analytic combinatorics uses techniques from complex analysis to solve problems in enumerative combinatorics, specifically to find asymptotic estimates for the coefficients of generating functions.[1][2][3]
History
[edit]One of the earliest uses of analytic techniques for an enumeration problem came from Srinivasa Ramanujan and G. H. Hardy's work on integer partitions,[4][5] starting in 1918, first using a Tauberian theorem and later the circle method.[6]
Walter Hayman's 1956 paper A Generalisation of Stirling's Formula is considered one of the earliest examples of the saddle-point method.[7][8][9]
In 1990, Philippe Flajolet and Andrew Odlyzko developed the theory of singularity analysis.[10]
In 2009, Philippe Flajolet and Robert Sedgewick wrote the book Analytic Combinatorics.
Some of the earliest work on multivariate generating functions started in the 1970s using probabilistic methods.[11][12]
Development of further multivariate techniques started in the early 2000s.[13]
Techniques
[edit]Meromorphic functions
[edit]If is a meromorphic function and is its pole closest to the origin with order , then[14]
- as
Tauberian theorem
[edit]If
- as
where and is a slowly varying function, then[15]
- as
See also the Hardy–Littlewood Tauberian theorem.
Circle Method
[edit]For generating functions with logarithms or roots, which have branch singularities.[16]
Darboux's method
[edit]If we have a function where and has a radius of convergence greater than and a Taylor expansion near 1 of , then[17]
See Szegő (1975) for a similar theorem dealing with multiple singularities.
Singularity analysis
[edit]If has a singularity at and
- as
where then[18]
- as
Saddle-point method
[edit]For generating functions including entire functions which have no singularities.[19][20]
Intuitively, the biggest contribution to the contour integral is around the saddle point and estimating near the saddle-point gives us an estimate for the whole contour.
If is an admissible function,[21] then[22][23]
- as
where .
See also the method of steepest descent.
Notes
[edit]- ^ Melczer 2021, pp. vii and ix.
- ^ Pemantle and Wilson 2013, pp. xi.
- ^ Flajolet and Sedgewick 2009, pp. ix.
- ^ Melczer 2021, pp. vii.
- ^ Pemantle and Wilson 2013, pp. 62-63.
- ^ Pemantle and Wilson 2013, pp. 62.
- ^ Pemantle and Wilson 2013, pp. 63.
- ^ Wilf 2006, pp. 197.
- ^ Flajolet and Sedgewick 2009, pp. 607.
- ^ Flajolet and Sedgewick 2009, pp. 438.
- ^ Melczer 2021, pp. 13.
- ^ Flajolet and Sedgewick 2009, pp. 650 and 717.
- ^ Melczer 2021, pp. 13-14.
- ^ Sedgewick 4, pp. 59
- ^ Flajolet and Sedgewick 2009, pp. 435. Hardy 1949, pp. 166. I use the form in which it is stated by Flajolet and Sedgewick.
- ^ Pemantle and Wilson 2013, pp. 55-56.
- ^ Wilf 2006, pp. 194.
- ^ Flajolet and Sedgewick 2009, pp. 393.
- ^ Wilf 2006, pp. 196.
- ^ Flajolet and Sedgewick 2009, pp. 542.
- ^ See Flajolet and Sedgewick 2009, pp. 565 or Wilf 2006, pp. 199.
- ^ Flajolet and Sedgewick 2009, pp. 553.
- ^ Sedgewick 8, pp. 25.
References
[edit]- Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
- Hardy, G.H. (1949). Divergent Series (1st ed.). Oxford University Press.
- Melczer, Stephen (2021). An Invitation to Analytic Combinatorics: From One to Several Variables (PDF). Springer Texts & Monographs in Symbolic Computation.
- Pemantle, Robin; Wilson, Mark C. (2013). Analytic Combinatorics in Several Variables (PDF). Cambridge University Press.
- Sedgewick, Robert. "4. Complex Analysis, Rational and Meromorphic Asymptotics" (PDF). Retrieved 4 November 2023.
- Sedgewick, Robert. "8. Saddle-Point Asymptotics" (PDF). Retrieved 4 November 2023.
- Szegő, Gabor (1975). Orthogonal Polynomials (4th ed.). American Mathematical Society.
- Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.
As of 4th November 2023, this article is derived in whole or in part from Wikibooks. The copyright holder has licensed the content in a manner that permits reuse under CC BY-SA 3.0 and GFDL. All relevant terms must be followed.
Further reading
[edit]![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/df/Wikibooks-logo-en-noslogan.svg/40px-Wikibooks-logo-en-noslogan.svg.png)
- De Bruijn, N.G. (1981). Asymptotic Methods in Analysis. Dover Publications.
- Flajolet, Philippe; Odlyzko, Andrew (1990). "Singularity analysis of generating functions" (PDF). SIAM Journal on Discrete Mathematics. 1990 (3).
- Mishna, Marni (2020). Analytic Combinatorics: A Multidimensional Approach. Taylor & Francis Group, LLC.
- Pemantle, Robin; Wilson, Mark C.; Melczer, Stephen (2024). Analytic Combinatorics in Several Variables (PDF) (2nd ed.). Cambridge University Press.
- Sedgewick, Robert. "6. Singularity Analysis" (PDF).
External links
[edit]- Analytic Combinatorics online course
- An Introduction to the Analysis of Algorithms online course
- Analytic Combinatorics in Several Variables projects
- An Invitation to Analytic Combinatorics