Analytic combinatorics

Last updated November 08, 2023

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

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

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

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

[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.^[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 $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

n\to \infty

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

Related Research Articles

In mathematics, the gamma function is one commonly used extension of the factorial function to complex numbers. The gamma function is defined for all complex numbers except the non-positive integers. For every positive integer $n$ ,

In physics, the Lorentz transformations are a six-parameter family of linear transformations from a coordinate frame in spacetime to another frame that moves at a constant velocity relative to the former. The respective inverse transformation is then parameterized by the negative of this velocity. The transformations are named after the Dutch physicist Hendrik Lorentz.

The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter $ζ$ (zeta), is a mathematical function of a complex variable defined as

In complex analysis, a branch of mathematics, analytic continuation is a technique to extend the domain of definition of a given analytic function. Analytic continuation often succeeds in defining further values of a function, for example in a new region where the infinite series representation which initially defined the function becomes divergent.

<span class="mw-page-title-main">Euler's constant</span> Relates logarithm and harmonic series

Euler's constant is a mathematical constant, usually denoted by the lowercase Greek letter gamma, defined as the limiting difference between the harmonic series and the natural logarithm, denoted here by $log$ :

In mechanics and geometry, the 3D rotation group, often denoted SO(3), is the group of all rotations about the origin of three-dimensional Euclidean space $under the operation of composition.$

In probability theory and statistics, the gamma distribution is a two-parameter family of continuous probability distributions. The exponential distribution, Erlang distribution, and chi-squared distribution are special cases of the gamma distribution. There are two equivalent parameterizations in common use:

With a shape parameter $and a scale parameter .$
With a shape parameter $and an inverse scale parameter, called a rate parameter.$

In mathematics, the Mellin transform is an integral transform that may be regarded as the multiplicative version of the two-sided Laplace transform. This integral transform is closely connected to the theory of Dirichlet series, and is often used in number theory, mathematical statistics, and the theory of asymptotic expansions; it is closely related to the Laplace transform and the Fourier transform, and the theory of the gamma function and allied special functions.

In mathematics, the Riemann–Siegel theta function is defined in terms of the gamma function as

In mathematics, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. It is an example of an important arithmetic function that is neither multiplicative nor additive.

In mathematics, Riemann's differential equation, named after Bernhard Riemann, is a generalization of the hypergeometric differential equation, allowing the regular singular points to occur anywhere on the Riemann sphere, rather than merely at 0, 1, and $. The equation is also known as the Papperitz equation .$

In mathematics, a Newtonian series, named after Isaac Newton, is a sum over a sequence $written in the form$

In mathematics, the reciprocal gamma function is the function

In mathematical finance, the SABR model is a stochastic volatility model, which attempts to capture the volatility smile in derivatives markets. The name stands for "stochastic alpha, beta, rho", referring to the parameters of the model. The SABR model is widely used by practitioners in the financial industry, especially in the interest rate derivative markets. It was developed by Patrick S. Hagan, Deep Kumar, Andrew Lesniewski, and Diana Woodward.

In mathematics, the multiplication theorem is a certain type of identity obeyed by many special functions related to the gamma function. For the explicit case of the gamma function, the identity is a product of values; thus the name. The various relations all stem from the same underlying principle; that is, the relation for one special function can be derived from that for the others, and is simply a manifestation of the same identity in different guises.

In number theory, an average order of an arithmetic function is some simpler or better-understood function which takes the same values "on average".

In mathematics, Montgomery's pair correlation conjecture is a conjecture made by Hugh Montgomery (1973) that the pair correlation between pairs of zeros of the Riemann zeta function is

Least-squares support-vector machines (LS-SVM) for statistics and in statistical modeling, are least-squares versions of support-vector machines (SVM), which are a set of related supervised learning methods that analyze data and recognize patterns, and which are used for classification and regression analysis. In this version one finds the solution by solving a set of linear equations instead of a convex quadratic programming (QP) problem for classical SVMs. Least-squares SVM classifiers were proposed by Johan Suykens and Joos Vandewalle. LS-SVMs are a class of kernel-based learning methods.

In mathematics, infinite compositions of analytic functions (ICAF) offer alternative formulations of analytic continued fractions, series, products and other infinite expansions, and the theory evolving from such compositions may shed light on the convergence/divergence of these expansions. Some functions can actually be expanded directly as infinite compositions. In addition, it is possible to use ICAF to evaluate solutions of fixed point equations involving infinite expansions. Complex dynamics offers another venue for iteration of systems of functions rather than a single function. For infinite compositions of a single function see Iterated function. For compositions of a finite number of functions, useful in fractal theory, see Iterated function system.

In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function or weighted sums over the higher-order derivatives of these functions.

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.