Analytic combinatorics uses techniques from complex analysis to find asymptotic estimates for the coefficients of generating functions.[1][2][3]
History
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
Meromorphic functions
If is a meromorphic function and is its pole closest to the origin with order , then[14]
- as
 
Tauberian theorem
If
- as
 
where and is a slowly varying function, then[15]
- as
 
See also the Hardy–Littlewood Tauberian theorem.
Circle Method
For generating functions with logarithms or roots, which have branch singularities.[16]
Darboux's method
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
If has a singularity at and
- as
 
where then[18]
- as
 
Saddle-point method
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
- ↑ 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
- 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
- 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.
 - Sedgewick, Robert. "6. Singularity Analysis" (PDF).