This article needs attention from an expert in Mathematics. Please add a reason or a talk parameter to this template to explain the issue with the article.(January 2024) |
Analytic combinatorics uses techniques from complex analysis 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.
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 is a meromorphic function and is its pole closest to the origin with order , then [14]
If
where and is a slowly varying function, then [15]
See also the Hardy–Littlewood Tauberian theorem.
For generating functions with logarithms or roots, which have branch singularities. [16]
If we have a function where and has a radius of convergence greater than and a Taylor expansion near 1 of , then [17]
See Szegő (1975) for a similar theorem dealing with multiple singularities.
If has a singularity at and
where then [18]
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 is an admissible function, [21] then [22] [23]
where .
See also the method of steepest descent.
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.
This article needs attention from an expert in Mathematics. Please add a reason or a talk parameter to this template to explain the issue with the article.(January 2024) |
Analytic combinatorics uses techniques from complex analysis 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.
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 is a meromorphic function and is its pole closest to the origin with order , then [14]
If
where and is a slowly varying function, then [15]
See also the Hardy–Littlewood Tauberian theorem.
For generating functions with logarithms or roots, which have branch singularities. [16]
If we have a function where and has a radius of convergence greater than and a Taylor expansion near 1 of , then [17]
See Szegő (1975) for a similar theorem dealing with multiple singularities.
If has a singularity at and
where then [18]
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 is an admissible function, [21] then [22] [23]
where .
See also the method of steepest descent.
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.