Analytic combinatorics
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]
Flajolet and Odlyzko
Flajolet and Sedgewick
Theorems
Tauberian theorems
Darboux
Meromorphic functions
Singularity analysis
Saddle-point method
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.
References
- Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge 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.
- Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.
Further reading
Wikibooks has a book on the topic of: Analytic_Combinatorics
- 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).
- Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge 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.
- Szegő, Gabor (1975). Orthogonal Polynomials (4th ed.). American Mathematical Society.
- Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.
External links
- Analytic Combinatorics online course
- An Introduction to the Analysis of Algorithms online course
- Analytic Combinatorics in Several Variables projects
- An Invitation to Analytic Combinatorics
- Philippe Flajolet's Home Page
- Andrew Odlyzko's Home Page