Analytic Combinatorics/Meromorphic Functions

Introduction This article explains how to estimate the coefficients of meromorphic generating functions which have only one dominant singularity. Theorem Theorem due to Sedgewick.Sedgewick, pp. 59. If is a meromorphic function which has one pole, , with order and any other poles, if they exist, have a larger modulus than then you can estimate its th coefficient with the formula:Sedgewick, (errata), pp. 8. Proof Proof due to SedgewickSedgewick, pp. 59-60. and WilfWilf 2006, pp. 185-186.. , being meromorphic, can be Laurent expanded around See Stroud 2003, pp. 919-923, Lang 1999, pp. 161-163, Orloff, pp. 10-13, w:Laurent_series, v:Complex_Analysis_in_plain_view#Laurent_Series_and_the_z-Transform_Example_Note.: this Laurent expansion can be estimated by its principle partWilf 2006, pp. 185-186.: contributes the biggest coefficient. Its th coefficient can be computed as: can be computed as: as (Proof) Therefore, putting it all together: as . Meromorphic function The above theorem only applies to a class of generating functions called meromorphic functions. A meromorphic function is the ratio of two analytic functions. This includes all rational functions (the ratio of two polynomials) such as and . One property of meromorphic functions is that they can be represented as Laurent series expansions, a fact we will use in the proof. It is possible to estimate the coefficients of functions which are not meromorphic (e.g. or ). These will be covered in future chapters. Laurent series When we want a series expansion of a function around a singularity , we cannot use the Taylor series expansion. Instead, we use the Laurent series expansionStroud 2003, pp. 919-920.: Where and is a contour in the annular region in which is analytic, illustrated below. 200px Pole A pole is a type of singularity. A singularity of is a value of for which This is a bit of an over-simplification. For further information, see Stroud 2003, pp. 863-867, 915 and w:Mathematical_singularity. If and is defined then is called a pole of of order Stroud 2003, pp. 915.. We will make use of this fact when we calculate . For example, has the singularity because and is a pole of order 2 because . Principle part Proof due to WilfWilf 2006, pp. 52, 185-186.. The principle part of a Laurent series expansion are the terms with a negative exponent, i.e. We will denote the principle part of at by . If is the pole closest to the origin then the radius of convergence and as a consequence of the Cauchy-Hadamard theoremWilf 2006, pp. 50-52.: (for some and for sufficiently large ) no longer has a pole at because . If the second closest pole to the origin of is then is the largest pole of and, by the above theorem, the coefficients of (for sufficiently large ). Therefore, the coefficients of are at most different from the coefficient of by (for sufficiently large ). Note that if is the only pole, the difference is at most (for sufficiently large ). If then as gets large will be much smaller than and, therefore, is a good enough approximation of . However, if then the behaviour of the coefficients is more complicated. Biggest coefficient Compare: See #Computation of coefficient of first term and #Proof of binomial asymptotics. with: The th coefficient of the former is only different to the latter by . Computation of coefficient of first term by factoring out . by the binomial theorem for negative exponentsBiggs 2002, pp. 364-366.. Computation of h_-m . Therefore, . To compute , because the numerator and denominator are both at , we need to use L'Hôpital's ruleStroud 2001, pp. 792, v:Calculus/Limits#L'Hôpital's_Rule, w:L'Hôpital's_rule.: Indeed, if is a root of order of and , it is also a root of and and therefore is also indeterminate. Therefore, we need to apply L'Hôpital's rule times: Proof of binomial asymptotics as . Notes References Biggs Norman L. Discrete Mathematics 2nd Oxford University Press 2002 Flajolet Philippe Sedgewick Robert Analytic Combinatorics Cambridge University Press 2009 https://ac.cs.princeton.edu/home/AC.pdf Lang Serge Complex Analysis 4th Springer Science+Business Media, LLC 1999 https://math.mit.edu/~jorloff/18.04/notes/topic7.pdf Topic 7 Notes: Taylor and Laurent series. Orloff Jeremy 3 October 2022 https://ac.cs.princeton.edu/online/slides/AC04-Poles.pdf 4. Complex Analysis, Rational and Meromorphic Asymptotics. Sedgewick Robert 16 September 2022 https://ac.cs.princeton.edu/online/slides/ACqa3.pdf 4. Complex Analysis, Rational and Meromorphic Asymptotics (Errata). Sedgewick Robert 16 September 2022 Stroud K. A. Advanced Engineering Mathematics 4th Palgrave Macmillan 2003 Stroud K. A. Engineering Mathematics 5th Palgrave Macmillan 2001 Wilf Herbert S. Generatingfunctionology 3rd A K Peters, Ltd 2006 https://www2.math.upenn.edu/~wilf/gfology2.pdf