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]

In 1990, Flajolet and Odlyzko developed the theory of singularity analysis.^[10]

In 2009, Flajolet and Sedgewick wrote the book Analytic Combinatorics.

Some of the earliest work on multivariate generating functions started in the 1970s using probabilistic methods.^[11]

Development of further multivariate techniques started in the early 2000s.^[12]

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

[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^[14]

[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.^[15]

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^[16]

[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^[17]

[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 which have no singularities.^[18]

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

[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.
^ Flajolet and Sedgewick 2009, pp. 438.
^ Melczer 2021, pp. 13. Flajolet and Sedgewick 2009, pp. 650 and 717.
^ 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.
^ Pemantle and Wilson 2013, pp. 55-56.
^ Wilf 2006, pp. 194.
^ Flajolet and Sedgewick 2009, pp. 393.
^ Wilf 2006, pp. 196. Flajolet and Sedgewick 2009, pp. 542.
^ See Flajolet and Sedgewick 2009, pp. 565 or Wilf 2006, pp. 199.
^ Flajolet and Sedgewick 2009, pp. 553. Sedgewick 8, pp. 25.

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

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.