Analytic 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.

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, starting in 1918, first using a Tauberian theorem and later the circle method.

Walter Hayman's 1956 paper "A Generalisation of Stirling's Formula" is considered one of the earliest examples of the saddle-point method.

In 1990, Philippe Flajolet and Andrew Odlyzko developed the theory of singularity analysis.

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.

Development of further multivariate techniques started in the early 2000s.

Techniques

Meromorphic functions

If $h(z) = \frac$ is a meromorphic function and $a$ is its pole closest to the origin with order $m$, then
: ^nh(z) \sim \frac \left( \frac \right)^n n^ \quad as $n \to \infty$

Tauberian theorem

If
:$f(z) \sim \frac L(\frac) \quad$ as $z \to 1$
where $\sigma > 0$ and $L$ is a slowly varying function, then
: ^n(z) \sim \frac L(n) \quad as $n \to \infty$

See also the Hardy–Littlewood Tauberian theorem.

Circle Method

For generating functions with logarithms or roots, which have branch singularities.

Darboux's method

If we have a function $(1 - z)^\beta f(z)$ where $\beta \notin \$ and $f(z)$ has a radius of convergence greater than $1$ and a Taylor expansion near 1 of $\sum_ f_j (1 - z)^j$, then
: ^n1 - z)^\beta f(z) = \sum_^m f_j \frac + O(n^)

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\right)^\alpha \left(\frac\log\frac\right)^\gamma \left(\frac\log\left(\frac\log\frac\right)\right)^\delta \quad$ as $z \to \zeta$

where $\alpha \notin \, \gamma, \delta \notin \$ then

: ^n(z) \sim \zeta^ \frac (\log n)^\gamma (\log\log n)^\delta \quad as $n \to \infty$

Saddle-point method

For generating functions including entire functions.

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, thenSedgewick 8, pp. 25.

: ^nF(z) \sim \frac \quad as $n \to \infty$

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

See also the method of steepest descent.

Notes

References

*
*
*
*
*
*
*
*

Further reading

*
*
*
*
*
* {{cite book , last=Wong , first=R. , title=Asymptotic Approximations of Integrals , publisher=Society for Industrial and Applied Mathematics , year=2001

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

See also

* Symbolic method (combinatorics)
* Analytic Combinatorics (book)

Enumerative combinatorics