Analytic Combinatorics/Shape of Functions

Introduction We start with an informal presentation of how to understand different sorts of generating functions in the context of analytic combinatorics and which techniques to apply to which functions. Little background knowledge of complex analysis is assumed. Representing generating functions in the complex plane We are used to seeing generating functions as formal objects. For example, unrestricted integer compositions have the below ordinary generating function and power series expansion.Flajolet and Sedgewick 2009, pp. 297. We can also see generating functions as "complex-analytic" functions: those whose input and output are complex numbers. A complex number has two components, a "real" and an "imaginary" part. Therefore, we can graph the above generating function as a three-dimensional landscape, the north-south and east-west plane measuring the real and imaginary parts of the input and the height of the graph measuring the magnitude of the output. 400px|Compositions visualised as a 3D surface. 400px|The same graph as seen from above, as a contour graph. Functions with one pole singularity Notice that there is a peak when the input has real part 0.5 and imaginary part 0. Actually, this peak should extend up to infinity but we are limited by our technology. This is because if we set then Where such a peak occurs is called a pole singularity. Therefore, for our function, we have a pole singularity at 1/2. We will see by the Cauchy-Hadamard theorem that, if we take the reciprocal of the singularity (i.e. 2), we can get upper and (with some caveats) lower bounds for our estimates of the coefficients. For any there are infinite such that . + Comparing the upper and lower bounds and the actual value of for e = 0.01 n 500 2.670165651072143E+149 1.636695303948071E+150 3.96304232182789E+151 750 1.379771935849753E+224 2.961193260766428E+225 2.49484210739009E+227 1000 7.129784604165516E+298 5.357543035931337E+300 1.5705704444599E+303 But, because our function has only one pole singularity, we can use an even better estimate for Meromorphic functions: (which is in fact the actual value of ). Other generating functions which have only one pole singularity include derangements and alignments. s(n, k) is the unsigned Stirling number of first kind Name Surface graph (Exponential) generating function Cauchy-Hadamard upper-bound Meromorphic estimate Actual value Derangements 200px Alignments 200px Sloane, N. J. A. (ed.). "Sequence A007840". Functions with more than one pole singularity Many generating functions have more than one pole singularity. Fortunately, the above analysis also applies if there is one pole closest to the origin and all other poles are further away. For example, the Fibonacci numbers with the ordinary generating function 400px 400px This has two poles at and .Flajolet and Sedgewick 2009, pp. 256. The nearest to the origin is . This gives us a Cauchy-Hadamard upper-bound of roughly and a meromorphic estimate of . It even works if there are an infinite number of pole singularities, such as in the case of surjections, with exponential generating function . 400px 400px This has poles at all points , with one of .Flajolet and Sedgewick 2009, pp. 245. The nearest to the origin is . This gives an upper-bound of and a meromorphic estimate of . Functions with multiple dominant pole singularities Some generating functions have multiple poles equidistant to the origin. For example, has two poles at and . 400px 400px Sadly, it is harder to work out estimates for these functions, as their coefficients have periodic behaviour. For example, the above function has expansion . We will see in Meromorphic Functions with Multiple Dominant Singularities what it is possible to say about such functions. Functions with different sorts of singularities Generating functions involving logarithms and roots have singularities different from poles, meaning we cannot apply the meromorphic formula presented above. These types of singularity, called branch points, only become apparent when we plot the output in terms not of its magnitude but of its argument, its angle from the real axis. Take the generating function for 2-regular graphs .Flajolet and Sedgewick 2009, pp. 133. 400px There is a discontinuity or "jump" along the real axis from 1 to . We can still apply Cauchy-Hadamard (with radius of convergence 1 in our example) or more sophisticated techniques from Darboux, Tauber and singularity analysis to say that the coefficients are approximately . Functions with singularities only at infinity The generating function has no singularity for any complex number except infinity. It is an entire function. Our strategy is derived from Cauchy's coefficient formula and involves the function , drawing a circle on its surface and integrating around it. 400px There are two ways of estimating this integral: Cauchy's inequality a simple formula giving us an upper-bound by integrating around the orange circle below, or the Saddle-point method where we concentrate on the highest part of the circle (in red below). 400px Notes References Flajolet Philippe Sedgewick Robert Analytic Combinatorics Cambridge University Press 2009 https://ac.cs.princeton.edu/home/AC.pdf Sloane, N. J. A. (ed.). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.