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]}

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]

If ${\displaystyle h(z)={\frac {f(z)}{g(z)}}}${\displaystyle h(z)={\frac {f(z)}{g(z)}}} is a meromorphic function and ${\displaystyle a}${\displaystyle a} is its pole closest to the origin with order ${\displaystyle m}${\displaystyle m}, then^[14]

${\displaystyle [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 }${\displaystyle [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 ${\displaystyle n\to \infty }${\displaystyle n\to \infty }

If

${\displaystyle f(z)\sim {\frac {1}{(1-z)^{\sigma }}}L({\frac {1}{1-z}})\quad }${\displaystyle f(z)\sim {\frac {1}{(1-z)^{\sigma }}}L({\frac {1}{1-z}})\quad } as ${\displaystyle z\to 1}${\displaystyle z\to 1}

where ${\displaystyle \sigma >0}${\displaystyle \sigma >0} and ${\displaystyle L}${\displaystyle L} is a slowly varying function, then^[15]

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

See also the Hardy–Littlewood Tauberian theorem.

For generating functions with logarithms or roots, which have branch singularities.^[16]

If we have a function ${\displaystyle (1-z)^{\beta }f(z)}${\displaystyle (1-z)^{\beta }f(z)} where ${\displaystyle \beta \notin \{0,1,2,\ldots \}}${\displaystyle \beta \notin \{0,1,2,\ldots \}} and ${\displaystyle f(z)}${\displaystyle f(z)} has a radius of convergence greater than ${\displaystyle 1}${\displaystyle 1} and a Taylor expansion near 1 of ${\displaystyle \sum _{j\geq 0}f_{j}(1-z)^{j}}${\displaystyle \sum _{j\geq 0}f_{j}(1-z)^{j}}, then^[17]

${\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})}${\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.

If ${\displaystyle f(z)}${\displaystyle f(z)} has a singularity at ${\displaystyle \zeta }${\displaystyle \zeta } and

${\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 }${\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 ${\displaystyle z\to \zeta }${\displaystyle z\to \zeta }

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

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

For generating functions including entire functions.^{[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 ${\displaystyle F(z)}${\displaystyle F(z)} is an admissible function,^[21] then^{[22] [23]}

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

where ${\displaystyle F^{'}(\zeta )=0}${\displaystyle F^{'}(\zeta )=0}.

See also the method of steepest descent.

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

• De Bruijn, N.G. (1981). Asymptotic Methods in Analysis. Dover Publications.
• Flajolet, Philippe; Odlyzko, Andrew (1990). "Singularity analysis of generating functions" (PDF). SIAM Journal on Discrete Mathematics. 1990 (3).
• Mishna, Marni (2020). Analytic Combinatorics: A Multidimensional Approach. Taylor & Francis Group, LLC.
• Pemantle, Robin; Wilson, Mark C.; Melczer, Stephen (2024). Analytic Combinatorics in Several Variables (PDF) (2nd ed.). Cambridge University Press.
• Sedgewick, Robert. "6. Singularity Analysis" (PDF).
• Wong, R. (2001). Asymptotic Approximations of Integrals. Society for Industrial and Applied Mathematics.

• Analytic Combinatorics online course
• An Introduction to the Analysis of Algorithms online course
• Analytic Combinatorics in Several Variables projects
• An Invitation to Analytic Combinatorics

• Symbolic method (combinatorics)
• Analytic Combinatorics (book)

• Enumerative combinatorics

• Articles needing expert attention with no reason or talk parameter
• Articles needing expert attention from January 2024
• All articles needing expert attention
• Mathematics articles needing expert attention
• Articles with imported dually licensed text