Analytic Combinatorics/Saddle-point Method

Theorem Theorem due to Flajolet and SedgewickFlajolet and Sedgewick 2009, pp. 553.. If is an admissible function then as where is such that and . Proof Proof due to Flajolet and SedgewickFlajolet and Sedgewick 2009, pp. 551-554.. By Cauchy's coefficient formula: We can visualise this as a 3D graph whose and axes are the real and imaginary parts of respectively and the axis is the real part of . 400px For the generating functions we are interested in, has a saddle-point on the positive real axisFlajolet and Sedgewick 2009, pp. 549.. This is the highest altitude of the green path in the above graph. Call this . Being an analytic function (except at ), we can deform the contour to go through the saddle-point. The biggest contributor to the integral is made by the part of the contour near the saddle-point (call this , which is the red part of the path in the graph below). The rest of the contour (call this , the green part of the path) contributes relatively little. 400px In the below, we set We can deform the contour even more to make the part of the contour near the saddle-point a straight line (in the complex plane). is deformed to a straight, vertical line, perpendicular to the real axis, crossing the saddle-point, starting from to . is chosen such that and as . This is so that the Taylor series expansion around . can be reduced to just . is real-valued because is real and , being a generating function, has real coefficients. , so is real. Therefore, is real-valued. So, any imaginary part of can be moved outside the integral, leaving just a real-valued integrand: This also means that the real-valued surface we discussed in the beginning is a valid estimate of the potentially complex-valued . We change variables to remove the imaginary part of the interval and turn it into a real-valued integrand over the real line. Setting : Because is very small for large : Due to our choice of before, as , . Therefore, the integral can be estimated by a Gaussian integral which we know how to calculate: Putting it all together: Admissibility This formalises the conditions under which we can apply the saddle-point method. Definition from Flajolet and SedgewickFlajolet and Sedgewick 2009, pp. 565. and WilfWilf 2006, pp. 199.. Also known as Hayman-admissibilityAfter Walter Hayman.. The function is admissible if: is a function with radius of convergence There exists an such that H1: and H2: There exists a function defined for such that and as uniformly for H3: Uniformly for and as Intuitive explanation To find the coefficients of a function, we can use the Cauchy coefficient formula. This requires us to find the integral of a path in the complex plane. Imagine trying to estimate this integral, displayed as the red and green line below. 400px The biggest contribution to the integral comes from around the saddle-point (displayed in red) and the tail's contribution (displayed in green) is negligible (by H3). Therefore, to estimate the integral of the entire path you can estimate the integral of just the red part of the path. This is the asymptotic relation described in H2. Example Example from WilfWilf 2006, pp. 198. and Flajolet and SedgewickFlajolet and Sedgewick 2009, pp. 555-557.. Say we want to estimate the coefficients of : has radius of convergence and is positive for all . H1: . Therefore, . H1: . Therefore, . Find the saddle-point by solving the equation . Therefore, and the path of integration is the circle of radius centred at the origin. Choose . H3: For as . H2: For (due to the power series expansion of ). Apply the theorem: . Saddle-points of higher order Theorem from Flajolet and SedgewickFlajolet and Sedgewick 2009, pp. 603.. The above assumes and . In the case where all derivatives up to the th are zero but , we call it a saddle-point of order or multiplicity Flajolet and Sedgewick 2009, pp. 545.. If has a saddle-point of order : where . Notes References Flajolet Philippe Sedgewick Robert Analytic Combinatorics Cambridge University Press 2009 https://ac.cs.princeton.edu/home/AC.pdf Wilf Herbert S. Generatingfunctionology 3rd A K Peters, Ltd 2006 https://www2.math.upenn.edu/~wilf/gfology2.pdf