Analytic combinatorics

Analytic combinatorics uses techniques from complex analysis to solve problems in enumerative combinatorics, specifically 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, which presents analytic combinatorics with their viewpoint and notation.

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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h(z) = \frac{f(z)}{g(z)}} is a meromorphic function and $a$ is its pole closest to the origin with order $m$ , then^[14]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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} as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \to \infty}

Tauberian theorem

If

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(z) \sim \frac{1}{(1 - z)^\sigma} L(\frac{1}{1 - z}) \quad} as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z \to 1}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma > 0} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} is a slowly varying function, then^[15]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [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.^[16]

Darboux's method

If we have a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1 - z)^\beta f(z)} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta \notin \{0, 1, 2, \ldots\}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(z)} has a radius of convergence greater than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} and a Taylor expansion near 1 of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{j\geq0} f_j (1 - z)^j} , then^[17]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(z)} has a singularity at $\zeta$ and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z \to \zeta}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha \notin \{0, 1, 2, \cdots\}, \gamma, \delta \notin \{1, 2, \cdots\}} then^[18]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [z^n]f(z) \sim \zeta^{-n} \frac{n^{-\alpha-1}}{\Gamma(-\alpha)} (\log n)^\gamma (\log\log n)^\delta \quad} as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(z)} is an admissible function,^[21] then^[22]^[23]

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

as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \to \infty}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F^'(\zeta) = 0} .

See also the method of steepest descent.

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.