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

Bender used the Central Limit Theorem for bivariate generating functions...^[10]

Multivariate, Wilson, Pemantle...^[11]

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$ , then^[12]

[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

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, then^[13]

[z^{n}]f(z)\sim {\frac {n^{\sigma -1}}{\Gamma (\sigma )}}L(n)\quad

as

n\to \infty

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 an expansion near 1 of $\sum _{j\geq 0}f_{j}(1-z)^{j}$ , then^[14]

[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 \}$ then^[15]

[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

If $F(z)$ is an admissible function^[16], then^[17]

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

as

n\to \infty

where $\zeta$ is such that $F^{'}(\zeta )=0$ .

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.
^ Melczer 2021, pp. 13.
^ Melczer 2021, pp. 13-14.
^ Sedgewick, pp. 59
^ Flajolet and Sedgewick 2009, pp. 435. Hardy 1949, pp. 166. I use the form in which it is stated by Flajolet and Sedgewick.
^ Wilf 2006, pp. 194.
^ Flajolet and Sedgewick 2009, pp. 393.
^ See Flajolet and Sedgewick 2009, pp. 565 or Wilf 2006, pp. 199.
^ Flajolet and Sedgewick 2009, pp. 553.

References

Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
Hardy, G.H. (1949). Divergent Series (1st ed.). Oxford 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.
Sedgewick, Robert. "4. Complex Analysis, Rational and Meromorphic Asymptotics" (PDF). Retrieved 4 November 2023.
Szegő, Gabor (1975). Orthogonal Polynomials (4th ed.). American Mathematical Society.
Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.