View source for Analytic combinatorics

{{Distinguish|Analytic Combinatorics (book)|Symbolic method (combinatorics)}}

{{Expert needed|1=Mathematics|date=January 2024}}

'''Analytic combinatorics''' uses techniques from [[complex analysis]] to solve problems in [[enumerative combinatorics]], specifically to find [[Asymptotic_analysis|asymptotic estimates]] for the coefficients of [[Generating_function|generating functions]].<ref>Melczer 2021, pp. vii and ix.</ref><ref>Pemantle and Wilson 2013, pp. xi.</ref><ref>Flajolet and Sedgewick 2009, pp. ix.</ref>

== History ==

One of the earliest uses of analytic techniques for an enumeration problem came from [[Srinivasa Ramanujan]] and [[G. H. Hardy]]'s work on [[Partition_function_(number_theory)|integer partitions]],<ref>Melczer 2021, pp. vii.</ref><ref>Pemantle and Wilson 2013, pp. 62-63.</ref> starting in 1918, first using a Tauberian theorem and later the [[Hardy–Littlewood circle method|circle method]].<ref>Pemantle and Wilson 2013, pp. 62.</ref>

[[Walter Hayman]]'s 1956 paper "A Generalisation of Stirling's Formula" is considered one of the earliest examples of the saddle-point method.<ref>Pemantle and Wilson 2013, pp. 63.</ref><ref>Wilf 2006, pp. 197.</ref><ref>Flajolet and Sedgewick 2009, pp. 607.</ref>

In 1990, [[Philippe Flajolet]] and [[Andrew Odlyzko]] developed the theory of singularity analysis.<ref>Flajolet and Sedgewick 2009, pp. 438.</ref>

In 2009, [[Philippe Flajolet]] and [[Robert_Sedgewick_(computer_scientist)|Robert Sedgewick]] wrote the book ''[[Analytic_Combinatorics_(book)|Analytic Combinatorics]]'', which presents analytic combinatorics with their viewpoint and notation.

Some of the earliest work on [[Generating_function#Bivariate_and_multivariate_generating_functions|multivariate generating functions]] started in the 1970s using probabilistic methods.<ref>Melczer 2021, pp. 13.</ref><ref>Flajolet and Sedgewick 2009, pp. 650 and 717.</ref>

Development of further multivariate techniques started in the early 2000s.<ref>Melczer 2021, pp. 13-14.</ref>

== Techniques ==

=== Meromorphic functions ===

If <math>h(z) = \frac{f(z)}{g(z)}</math> is a [[meromorphic function]] and <math>a</math> is its [[Zeros_and_poles|pole]] closest to the origin with order <math>m</math>, then<ref>Sedgewick 4, pp. 59</ref>
:<math>[z^n] h(z) \sim \frac{(-1)^m m f(a)}{a^m g^{(m)}(a)} \left( \frac{1}{a} \right)^n n^{m-1} \quad</math> as <math>n \to \infty</math>

=== Tauberian theorem ===

If
:<math>f(z) \sim \frac{1}{(1 - z)^\sigma} L(\frac{1}{1 - z}) \quad</math> as <math>z \to 1</math>
where <math>\sigma > 0</math> and <math>L</math> is a [[slowly varying function]], then<ref>Flajolet and Sedgewick 2009, pp. 435. Hardy 1949, pp. 166. I use the form in which it is stated by Flajolet and Sedgewick.</ref>
:<math>[z^n]f(z) \sim \frac{n^{\sigma-1}}{\Gamma(\sigma)} L(n) \quad</math> as <math>n \to \infty</math>

See also the [[Hardy–Littlewood Tauberian theorem]].

=== Circle Method ===

For generating functions with [[Logarithm|logarithms]] or [[Nth_root|roots]], which have [[Singularity_(mathematics)#Branch_points|branch singularities]].<ref>Pemantle and Wilson 2013, pp. 55-56.</ref>

==== Darboux's method ====

If we have a function <math>(1 - z)^\beta f(z)</math> where <math>\beta \notin \{0, 1, 2, \ldots\}</math> and <math>f(z)</math> has a [[radius of convergence]] greater than <math>1</math> and a [[Taylor_series|Taylor expansion]] near 1 of <math>\sum_{j\geq0} f_j (1 - z)^j</math>, then<ref>Wilf 2006, pp. 194.</ref>
:<math>[z^n](1 - z)^\beta f(z) = \sum_{j=0}^m f_j \frac{n^{-\beta-j-1}}{\Gamma(-\beta-j)} + O(n^{-m-\beta-2})</math>

See [[#CITEREFSzegő1975|Szegő (1975)]] for a similar theorem dealing with multiple singularities.

==== Singularity analysis ====

If <math>f(z)</math> has a singularity at <math>\zeta</math> and

:<math>f(z) \sim \left(1 - \frac{z}{\zeta}\right)^\alpha \left(\frac{1}{\frac{z}{\zeta}}\log\frac{1}{1 - \frac{z}{\zeta}}\right)^\gamma \left(\frac{1}{\frac{z}{\zeta}}\log\left(\frac{1}{\frac{z}{\zeta}}\log\frac{1}{1 - \frac{z}{\zeta}}\right)\right)^\delta \quad</math> as <math>z \to \zeta</math>

where <math>\alpha \notin \{0, 1, 2, \cdots\}, \gamma, \delta \notin \{1, 2, \cdots\}</math>  then<ref>Flajolet and Sedgewick 2009, pp. 393.</ref>

:<math>[z^n]f(z) \sim \zeta^{-n} \frac{n^{-\alpha-1}}{\Gamma(-\alpha)} (\log n)^\gamma (\log\log n)^\delta \quad</math> as <math>n \to \infty</math>

=== Saddle-point method ===

For generating functions including [[Entire_function|entire functions]] which have no singularities.<ref>Wilf 2006, pp. 196.</ref><ref>Flajolet and Sedgewick 2009, pp. 542.</ref>

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 <math>F(z)</math> is an admissible function,<ref>See Flajolet and Sedgewick 2009, pp. 565 or Wilf 2006, pp. 199.</ref> then<ref>Flajolet and Sedgewick 2009, pp. 553.</ref><ref>Sedgewick 8, pp. 25.</ref>

:<math>[z^n] F(z) \sim \frac{F(\zeta)}{\zeta^{n+1} \sqrt{2 \pi f^{''}(\zeta)}} \quad</math> as <math>n \to \infty</math>

where <math>F^'(\zeta) = 0</math>.

See also the [[method of steepest descent]].

== Notes ==
{{Reflist}}

== References ==
* {{cite book | last1=Flajolet | first1=Philippe | last2=Sedgewick | first2=Robert | title=Analytic Combinatorics | publisher=Cambridge University Press | year=2009 | url=https://ac.cs.princeton.edu/home/AC.pdf }}
* {{cite book | last=Hardy | first=G.H. | title=Divergent Series | edition=1st | publisher=Oxford University Press | year=1949 }}
* {{cite book | last=Melczer | first=Stephen | title=An Invitation to Analytic Combinatorics: From One to Several Variables | publisher=Springer Texts & Monographs in Symbolic Computation | year=2021 | url=https://melczer.ca/files/Melczer-SubmittedManuscript.pdf }}
* {{cite book | last1=Pemantle | first1=Robin | last2=Wilson | first2=Mark C. | title=Analytic Combinatorics in Several Variables | publisher=Cambridge University Press | year=2013 | url=https://acsvproject.com/ACSV121108submitted.pdf }}
* {{cite web | url=https://ac.cs.princeton.edu/online/slides/AC04-Poles.pdf | title=4. Complex Analysis, Rational and Meromorphic Asymptotics. | last=Sedgewick | first=Robert | access-date=4 November 2023 }}
* {{cite web | url=https://ac.cs.princeton.edu/online/slides/AC08-Saddle.pdf | title=8. Saddle-Point Asymptotics | last=Sedgewick | first=Robert | access-date=4 November 2023 }}
* {{cite book | last=Szegő | first=Gabor | title=Orthogonal Polynomials | edition=4th | publisher=American Mathematical Society | year=1975 }}
* {{cite book | last=Wilf | first=Herbert S. | title=Generatingfunctionology | edition=3rd | publisher=A K Peters, Ltd | year=2006 | url=https://www2.math.upenn.edu/~wilf/gfology2.pdf }}

{{Dual|source=Wikibooks|sourcepath=https://en.wikibooks.org/wiki/Analytic_Combinatorics|date=4th November 2023}}

== Further reading ==
{{Wikibook|Analytic Combinatorics}}
* {{cite book | last=De Bruijn | first=N.G. | title=Asymptotic Methods in Analysis | publisher=Dover Publications | year=1981 }}
* {{cite journal | last1=Flajolet | first1=Philippe | last2=Odlyzko | first2=Andrew | title=Singularity analysis of generating functions | year=1990 | journal=SIAM Journal on Discrete Mathematics | volume=1990 | issue=3 | url=http://www.dtc.umn.edu/~odlyzko/doc/arch/singularity.anal.pdf }}
* {{cite book | last=Mishna | first=Marni | title=Analytic Combinatorics: A Multidimensional Approach | publisher=Taylor & Francis Group, LLC | year=2020 }}
* {{cite book | last1=Pemantle | first1=Robin | last2=Wilson | first2=Mark C. | last3=Melczer | first3=Stephen | title=Analytic Combinatorics in Several Variables | publisher=Cambridge University Press | year=2024 | edition=2nd | url=https://acsvproject.com/PemantleWilsonMelczer23.pdf }}
* {{cite web | url=https://ac.cs.princeton.edu/online/slides/AC06-SA.pdf | title=6. Singularity Analysis | last=Sedgewick | first=Robert }}

== External links ==
* [https://ac.cs.princeton.edu/home/ Analytic Combinatorics online course]
* [https://aofa.cs.princeton.edu/online/ An Introduction to the Analysis of Algorithms online course]
* [https://acsvproject.com Analytic Combinatorics in Several Variables projects]
* [https://melczer.ca/textbook/ An Invitation to Analytic Combinatorics]

== See also ==
* [[Symbolic method (combinatorics)]]
* [[Analytic Combinatorics (book)]]

[[Category:Enumerative combinatorics]]