analytic combinatorics

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

Analytic combinatorics uses techniques from complex analysis to solve problems in enumerative combinatorics, specifically to find asymptotic estimates for the coefficients of generating functions.Melczer 2021, pp. vii and ix.Pemantle and Wilson 2013, pp. xi.Flajolet and Sedgewick 2009, pp. ix.

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,Melczer 2021, pp. vii.Pemantle and Wilson 2013, pp. 62-63. starting in 1918, first using a Tauberian theorem and later the circle method.Pemantle and Wilson 2013, pp. 62.

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

In 1990, Philippe Flajolet and Andrew Odlyzko developed the theory of singularity analysis.Flajolet and Sedgewick 2009, pp. 438.

In 2009, Philippe Flajolet and Robert Sedgewick wrote the book Analytic Combinatorics, which presents analytic combinatorics with their viewpoint and notation.

Some of the earliest work on multivariate generating functions started in the 1970s using probabilistic methods.Melczer 2021, pp. 13.Flajolet and Sedgewick 2009, pp. 650 and 717.

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

Techniques

= Meromorphic functions =

If $h(z) = \frac{f(z)}{g(z)}$ is a meromorphic function and $a$ is its pole closest to the origin with order $m$ , thenSedgewick 4, pp. 59

: $[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$ as $n \to \infty$

= Tauberian theorem =

If

: $f(z) \sim \frac{1}{(1 - z)^\sigma} L(\frac{1}{1 - z}) \quad$ as $z \to 1$

where $\sigma > 0$ and $L$ is a slowly varying function, thenFlajolet and Sedgewick 2009, pp. 435. Hardy 1949, pp. 166. I use the form in which it is stated by Flajolet and Sedgewick.

: $[z^n]f(z) \sim \frac{n^{\sigma-1}}{\Gamma(\sigma)} L(n) \quad$ as $n \to \infty$

= Circle Method =

For generating functions with logarithms or roots, which have branch singularities.Pemantle and Wilson 2013, pp. 55-56.

== Darboux's method ==

If we have a function $(1 - z)^\beta f(z)$ where $\beta \notin \{0, 1, 2, \ldots\}$ and $f(z)$ has a radius of convergence greater than $1$ and a Taylor expansion near 1 of $\sum_{j\geq0} f_j (1 - z)^j$ , thenWilf 2006, pp. 194.

: $[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})$

See Szegő (1975) for a similar theorem dealing with multiple singularities.

== Singularity analysis ==

If $f(z)$ has a singularity at $\zeta$ and

: $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$ as $z \to \zeta$

where $\alpha \notin \{0, 1, 2, \cdots\}, \gamma, \delta \notin \{1, 2, \cdots\}$ thenFlajolet and Sedgewick 2009, pp. 393.

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

= Saddle-point method =

For generating functions including entire functions.Wilf 2006, pp. 196.Flajolet and Sedgewick 2009, pp. 542.

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

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

where $F^'(\zeta) = 0$ .

See also the method of steepest descent.

Notes

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}}

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]