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 ${\displaystyle h(z)={\frac {f(z)}{g(z)))}$ is a meromorphic function and ${\displaystyle a}$ is its pole closest to the origin with order ${\displaystyle m}$, then^[14]

${\displaystyle [z^{n}]h(z)\sim {\frac {(-1)^{m}mf(a)}{a^{m}g^{(m)}(a)))\left({\frac {1}{a))\right)^{n}n^{m-1}\quad }$ as ${\displaystyle n\to \infty }$

Tauberian theorem

If

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

where ${\displaystyle \sigma >0}$ and ${\displaystyle L}$ is a slowly varying function, then^[15]

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

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 ${\displaystyle (1-z)^{\beta }f(z)}$ where ${\displaystyle \beta \notin \{0,1,2,\ldots \))$ and ${\displaystyle f(z)}$ has a radius of convergence greater than ${\displaystyle 1}$ and a Taylor expansion near 1 of ${\displaystyle \sum _{j\geq 0}f_{j}(1-z)^{j))$, then^[17]

${\displaystyle [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 ${\displaystyle f(z)}$ has a singularity at ${\displaystyle \zeta }$ and

${\displaystyle 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 ${\displaystyle z\to \zeta }$

where ${\displaystyle \alpha \notin \{0,1,2,\cdots \},\gamma ,\delta \notin \{1,2,\cdots \))$ then^[18]

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

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 ${\displaystyle F(z)}$ is an admissible function,^[21] then^[22][23]

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

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

See also the method of steepest descent.