Recently, I was looking for good motivating examples for complex analysis in several variables. There was already a short discussion of this question at MathOverflow. Some further searching led me to the book Analytic Combinatorics in Several Variables by Robin Pemantle and Mark C. Wilson. What is this all about and why did I fall in love immediately?
Generating functions are one of the most magical objects in mathematics. Let us look at a first example in only one variable: the Fibonacci sequence. (This example and much more can be found in the book generatingfunctionology by Herbert Wilf.)
The Fibonacci sequence is defined recursively as:
Can we find a closed form solution for ?
One way to do so is by setting up the generating function . This is a formal sum, the mathematical way of hanging the Fibonacci numbers on a long clothes line and labelling the -th peg by :
In order to find , we need to find the coefficient of in . Nothing won? Well, let’s see how far we can get by manipulating .
Our original recursion tells us that . (We get this by multiplying each side by and then summing over .)
We can express this in terms of as follows (write out the sums to see this):
We can solve this for to get .
With the help of partial fraction decomposition, using the factorisation of the denominator, and using the abbreviation , we find that
Developing the right hand side into geometric series, we get:
From this we can read off the -th Fibonacci number as the coefficient of in the series:
Generating functions will not always give us closed form solutions like this but they can often give us very good asymptotics for combinatorial problems. Let’s go one step further and look at how a generating function in several variables can give us such information.
The combinatorial problem we will consider is that of computing asymptotics for the so-called Delannoy numbers. The Delannoy number gives the number of paths in the grid starting at position , ending at position , and taking steps of the form , , or .
If we set up the generating function
for this, we can use a similar trick as for the Fibonacci numbers to find a rational function form for this. For all pairs , we have the recurrence
where each term comes from one of the three possible steps in a path. Summing this over all , we get
Now putting in again and cleaning up any terms of the form and gives us all we need to find the expression we are looking for:
Hence, using the fact that , this yields
As mentioned above, we usually cannot expect to find a closed-form solution. However, there is a very useful tool from complex analysis for finding asymptotics: Cauchy’s integral formula. If our generating function is given by a function as above, we can recover the coefficients by contour integration:
(Here, , , and are vectors of dimension corresponding to the number of variables in our generating function, is a product of sufficiently small circles around the origin of each coordinate axis.)
In their paper Twenty combinatorial examples of asymptotics derived from multivariate generating functions, Pemantle and Wilson give a general recipe on how to evaluate this integral in the multivariate case if is rational of the form for polynomials and to find asymptotics for where the direction is suitably controlled. A central role is played by the geometry imposed by the zeros of . This is how the recipe is summarised (very closely following the text by Pemantle and Wilson):
- To find asymptotics in the direction , look at the geometry of the variety near a certain set of critical points.
- The set of critical points can be reduced to a subset of so-called contributing critical points which can be determined by a combination of algebraic and geometric criteria.
- The critical points come in three flavours: smooth, multiple, and bad.
- For each smooth or critical point there is an expansion for in terms of the derivatives of and .
- No general such expansion is known for bad points.
This should be vague enough to make you look up the details in the paper or the book.
Let me close by stating the result for the Delannoy numbers:
(I particularly like the fact that a Gröbner basis is used for handling in the derivation of this result.)
One thought on “A Beautiful Analytic Combination”
Pingback: The Power of Involutions | Glimpses of a fascinating world