Analytic combinatorics

From HandWiki

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

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

Tauberian theorem

If

[math]\displaystyle{ f(z) \sim \frac{1}{(1 - z)^\sigma} L(\frac{1}{1 - z}) \quad }[/math] as [math]\displaystyle{ z \to 1 }[/math]

where [math]\displaystyle{ \sigma \gt 0 }[/math] and [math]\displaystyle{ L }[/math] is a slowly varying function, then[15]

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

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

[math]\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}) }[/math]

See Szegő (1975) for a similar theorem dealing with multiple singularities.

Singularity analysis

If [math]\displaystyle{ f(z) }[/math] has a singularity at [math]\displaystyle{ \zeta }[/math] and

[math]\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 }[/math] as [math]\displaystyle{ z \to \zeta }[/math]

where [math]\displaystyle{ \alpha \notin \{0, 1, 2, \cdots\}, \gamma, \delta \notin \{1, 2, \cdots\} }[/math] then[18]

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

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

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

where [math]\displaystyle{ F^'(\zeta) = 0 }[/math].

See also the method of steepest descent.

Notes

  1. ↑ Melczer 2021, pp. vii and ix.
  2. ↑ Pemantle and Wilson 2013, pp. xi.
  3. ↑ Flajolet and Sedgewick 2009, pp. ix.
  4. ↑ Melczer 2021, pp. vii.
  5. ↑ Pemantle and Wilson 2013, pp. 62-63.
  6. ↑ Pemantle and Wilson 2013, pp. 62.
  7. ↑ Pemantle and Wilson 2013, pp. 63.
  8. ↑ Wilf 2006, pp. 197.
  9. ↑ Flajolet and Sedgewick 2009, pp. 607.
  10. ↑ Flajolet and Sedgewick 2009, pp. 438.
  11. ↑ Melczer 2021, pp. 13.
  12. ↑ Flajolet and Sedgewick 2009, pp. 650 and 717.
  13. ↑ Melczer 2021, pp. 13-14.
  14. ↑ Sedgewick 4, pp. 59
  15. ↑ Flajolet and Sedgewick 2009, pp. 435. Hardy 1949, pp. 166. I use the form in which it is stated by Flajolet and Sedgewick.
  16. ↑ Pemantle and Wilson 2013, pp. 55-56.
  17. ↑ Wilf 2006, pp. 194.
  18. ↑ Flajolet and Sedgewick 2009, pp. 393.
  19. ↑ Wilf 2006, pp. 196.
  20. ↑ Flajolet and Sedgewick 2009, pp. 542.
  21. ↑ See Flajolet and Sedgewick 2009, pp. 565 or Wilf 2006, pp. 199.
  22. ↑ Flajolet and Sedgewick 2009, pp. 553.
  23. ↑ Sedgewick 8, pp. 25.

References


Further reading

External links

See also



Retrieved from "https://handwiki.org/wiki/index.php?title=Analytic_combinatorics&oldid=3432110"