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 a Taylor 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 $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 4, 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. Sedgewick 8, pp. 25.

References

As of 4th November 2023, this article is derived in whole or in part from Wikibooks. The copyright holder has licensed the content in a manner that permits reuse under CC BY-SA 3.0 and GFDL. All relevant terms must be followed. The original text was at "Analytic Combinatorics"

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.
Sedgewick, Robert. "8. Saddle-Point 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.