# Analytic Combinatorics/Meromorphic Functions

## Introduction

This article explains how to estimate the coefficients of meromorphic generating functions.

## Theorem

Theorem due to Sedgewick[1].

• If ${\displaystyle h(z)={\frac {f(z)}{g(z)}}}$ is a meromorphic function
• and ${\displaystyle a}$ is its pole closest to the origin with order ${\displaystyle m}$
• then you can estimate its ${\displaystyle n}$th coefficient with the formula[2]:
${\displaystyle {\frac {(-1)^{m}mf(a)}{a^{m}g^{(m)}(a)}}\left({\frac {1}{a}}\right)^{n}n^{m-1}}$

## Proof

Proof due to Sedgewick[3] and Wilf[4].

• ${\displaystyle h(z)}$, being meromorphic, can be Laurent expanded around ${\displaystyle a}$[5]:
${\displaystyle h(z)={\frac {h_{-m}}{(z-a)^{m}}}+\cdots +{\frac {h_{-1}}{z-a}}+h_{0}+h_{1}(z-a)+\cdots }$
${\displaystyle {\frac {h_{-m}}{(z-a)^{m}}}+\cdots +{\frac {h_{-1}}{z-a}}}$
• ${\displaystyle {\frac {h_{-m}}{(z-a)^{m}}}}$ contributes the biggest coefficient. Its ${\displaystyle n}$th coefficient can be computed as:
${\displaystyle {\frac {(-1)^{m}h_{-m}}{a^{m}}}{\binom {n+m-1}{n}}\left({\frac {1}{a}}\right)^{n}}$
• ${\displaystyle h_{-m}}$ can be computed as:
${\displaystyle \lim _{z\to a}(z-a)^{m}h(z)={\frac {m!f(a)}{g^{(m)}(a)}}}$
• ${\displaystyle {\binom {n+m-1}{n}}\sim {\frac {n^{m-1}}{(m-1)!}}}$ as ${\displaystyle n\to \infty }$ (Proof)
• Therefore, putting it all together:
${\displaystyle [z^{n}]h(z)\sim {\frac {(-1)^{m}h_{-m}}{a^{m}}}{\binom {n+m-1}{n}}\left({\frac {1}{a}}\right)^{n}\sim {\frac {(-1)^{m}mf(a)}{a^{m}g^{(m)}(a)}}\left({\frac {1}{a}}\right)^{n}n^{m-1}}$ as ${\displaystyle n\to \infty }$.

## Asymptotic equality

We will make use of the asymptotic equality

${\displaystyle f(z)\sim g(z)}$ as ${\displaystyle z\to \zeta }$

which means

${\displaystyle \lim _{z\to \zeta }{\frac {f(z)}{g(z)}}=1}$

This allows us to use ${\displaystyle g(z)}$ as an estimate of ${\displaystyle f(z)}$ as ${\displaystyle z}$ gets closer to ${\displaystyle \zeta }$.

For example, we often present results of the form

${\displaystyle a_{n}\sim g(n)}$ as ${\displaystyle n\to \infty }$

which means, for large ${\displaystyle n}$, ${\displaystyle g(n)}$ becomes a good estimate of ${\displaystyle a_{n}}$.

## Meromorphic function

The above theorem only applies to a class of generating functions called meromorphic functions. This includes all rational functions (the ratio of two polynomials) such as ${\displaystyle {\frac {1}{(1-z)^{2}}}}$ and ${\displaystyle {\frac {z}{1-z-z^{2}}}}$.

A meromorphic function is the ratio of two analytic functions. An analytic function is a function whose complex derivative exists[7].

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. ${\displaystyle ln(z)}$ or ${\displaystyle e^{z}}$). These will be covered in future chapters.

## Laurent series

When we want a series expansion of a function ${\displaystyle f(z)}$ around a singularity ${\displaystyle c}$, we cannot use the Taylor series expansion. Instead, we use the Laurent series expansion[8]:

${\displaystyle \cdots +{\frac {a_{-2}}{(z-c)^{2}}}+{\frac {a_{-1}}{z-c}}+a_{0}+a_{1}(z-c)+a_{2}(z-c)^{2}+\cdots }$

Where ${\displaystyle a_{n}={\frac {1}{2\pi i}}\int _{\gamma }{\frac {f(z)}{(z-c)^{n+1}}}dz}$ and ${\displaystyle \gamma }$ is a contour in the annular region in which ${\displaystyle f(z)}$ is analytic, illustrated below.

## Pole

A pole is a type of singularity.

A singularity of ${\displaystyle h(z)}$ is a value of ${\displaystyle z}$ for which ${\displaystyle h(z)=\infty }$[9]

If ${\displaystyle \lim _{z\to a}(z-a)^{m}h(z)=L\neq 0}$ and ${\displaystyle L}$ is defined then ${\displaystyle a}$ is called a pole of ${\displaystyle h(z)}$ of order ${\displaystyle m}$[10].

We will make use of this fact when we calculate ${\displaystyle h_{-m}}$.

For example, ${\displaystyle {\frac {1}{(1-2z)^{2}}}}$ has the singularity ${\displaystyle {\frac {1}{2}}}$ because ${\displaystyle {\frac {1}{(1-2{\frac {1}{2}})^{2}}}={\frac {1}{(1-1)^{2}}}={\frac {1}{0^{2}}}={\frac {1}{0}}=\infty }$ and ${\displaystyle {\frac {1}{2}}}$ is a pole of order 2 because ${\displaystyle \lim _{z\to {\frac {1}{2}}}(z-{\frac {1}{2}})^{2}{\frac {1}{(1-2z)^{2}}}=\lim _{z\to {\frac {1}{2}}}(z-{\frac {1}{2}})^{2}{\frac {1}{(-2)^{2}(z-{\frac {1}{2}})^{2}}}=\lim _{z\to {\frac {1}{2}}}{\frac {1}{(-2)^{2}}}={\frac {1}{4}}}$.

## Closest to the origin

We are treating ${\displaystyle h(z)}$ as a complex function where the input ${\displaystyle z}$ is a complex number.

A complex number has two parts, a real part (Re) and an imaginary part (Im). Therefore, if we want to represent a complex number we do so in a two-dimensional graph.

If we want to compare the "size" of two complex numbers, we compare how far they are away from the origin in the two-dimensional plane (i.e. the length of the blue arrow in the above image). This is called the modulus, denoted ${\displaystyle |z|}$.

## Principle part

Proof due to Wilf[11].

The principle part of a Laurent series expansion are the terms with a negative exponent, i.e.

${\displaystyle {\frac {h_{-m}}{(z-a)^{m}}}+\cdots +{\frac {h_{-1}}{z-a}}}$

We will denote the principle part of ${\displaystyle h(z)}$ at ${\displaystyle a}$ by ${\displaystyle PP(h,a)}$.

If ${\displaystyle a}$ is the pole closest to the origin then the radius of convergence ${\displaystyle R=|a|}$ and as a consequence of the Cauchy-Hadamard theorem[12]:

${\displaystyle \left({\frac {1}{|a|}}-\epsilon \right)^{n}\leq [z^{n}]h(z)\leq \left({\frac {1}{|a|}}+\epsilon \right)^{n}}$ (for some ${\displaystyle \epsilon >0}$ and for sufficiently large ${\displaystyle n}$).

Where ${\displaystyle [z^{n}]h(z)}$ is the ${\displaystyle n}$th coefficient of ${\displaystyle h(z)}$.

${\displaystyle h(z)-PP(z)}$ no longer has a pole at ${\displaystyle a}$ because ${\displaystyle \left({\frac {h_{-m}}{(z-a)^{m}}}+\cdots +{\frac {h_{-}1}{z-a}}+h_{0}+h_{1}(z-a)+\cdots \right)-\left({\frac {h_{-m}}{(z-a)^{m}}}+\cdots +{\frac {h_{-1}}{z-a}}\right)=h_{0}+h_{1}(z-a)+\cdots }$.

If the second closest pole to the origin of ${\displaystyle h(z)}$ is ${\displaystyle a'}$ then ${\displaystyle a'}$ is the largest pole of ${\displaystyle h(z)-PP(z)}$ and, by the above theorem, the coefficients of ${\displaystyle h(z)-PP(h,a)\leq \left({\frac {1}{|a'|}}+\epsilon \right)^{n}}$ (for sufficiently large ${\displaystyle n}$).

Therefore, the coefficients of ${\displaystyle PP(h,a)}$ are at most different from the coefficient of ${\displaystyle h(z)}$ by ${\displaystyle \left({\frac {1}{|a'|}}+\epsilon \right)^{n}}$ (for sufficiently large ${\displaystyle n}$).

Note that if ${\displaystyle a}$ is the only pole, the difference is at most ${\displaystyle \epsilon ^{n}}$ (for sufficiently large ${\displaystyle n}$).

If ${\displaystyle a', then we may stop at ${\displaystyle PP(h,a)}$ as a good enough approximation.

However, if ${\displaystyle a'=a}$ then the coefficients of ${\displaystyle PP(h,a)}$ are different from ${\displaystyle h(z)}$ by as much as ${\displaystyle \left({\frac {1}{|a|}}+\epsilon \right)^{n}}$. This difference is as big as the coefficients of ${\displaystyle PP(h,a)}$. This is not a very good approximation. So, if there are other poles at the same distance to the origin it is a good idea to use all of them.

## Biggest coefficient

Compare:

${\displaystyle [z^{n}]{\frac {h_{-m}}{(z-a)^{m}}}={\frac {h_{-m}}{a^{m}}}{\binom {n+m-1}{n}}\left({\frac {1}{a}}\right)^{n}\sim {\frac {h_{-m}}{a^{m}}}\left({\frac {1}{a}}\right)^{n}n^{m-1}}$[13]

with:

${\displaystyle [z^{n}]{\frac {h_{-(m-1)}}{(z-a)^{m-1}}}={\frac {h_{-(m-1)}}{a^{m-1}}}{\binom {n+m-2}{n}}\left({\frac {1}{a}}\right)^{n}\sim {\frac {h_{-(m-1)}}{a^{m-1}}}\left({\frac {1}{a}}\right)^{n}n^{m-2}}$

The ${\displaystyle n}$th coefficient of the former is only different to the latter by ${\displaystyle O({\frac {n^{m-2}}{a^{n}}})}$.

## Computation of coefficient of first term

${\displaystyle {\frac {h_{-m}}{(z-a)^{m}}}={\frac {(-1)^{m}h_{-m}}{a^{m}(1-{\frac {z}{a}})^{m}}}}$ by factoring out ${\displaystyle \left({\frac {-1}{a}}\right)^{m}}$.

${\displaystyle {\frac {(-1)^{m}h_{-m}}{a^{m}(1-{\frac {z}{a}})^{m}}}={\frac {(-1)^{m}h_{-m}}{a^{m}}}\sum _{n\geq 0}{\binom {n+m-1}{n}}\left({\frac {z}{a}}\right)^{n}}$ by the binomial theorem for negative exponents[14].

## Computation of h_-m

${\displaystyle h(z)={\frac {h_{-m}}{(z-a)^{m}}}+{\frac {h_{-(m-1)}}{(z-a)^{m-1}}}+\cdots +{\frac {h_{-}1}{z-a}}+h_{0}+h_{1}(z-a)+\cdots }$.

Therefore, ${\displaystyle \lim _{z\to a}(z-a)^{m}h(z)=\lim _{z\to a}h_{-m}+h_{-(m-1)}(z-a)+\cdots +h_{-}1(z-a)^{m-1}+h_{0}(z-a)^{m}+h_{1}(z-a)^{m+1}+\cdots =h_{-m}}$.

To compute ${\displaystyle \lim _{z\to a}(z-a)^{m}h(z)=\lim _{z\to a}{\frac {(z-a)^{m}f(z)}{g(z)}}}$, because the numerator and denominator are both ${\displaystyle 0}$ at ${\displaystyle a}$, we need to use L'Hôpital's rule[15]:

${\displaystyle \lim _{z\to a}{\frac {(z-a)^{m}f(z)}{g(z)}}=\lim _{z\to a}{\frac {((z-a)^{m}f(z))'}{g'(z)}}}$

Indeed, if ${\displaystyle a}$ is a root of order ${\displaystyle m>1}$ of ${\displaystyle g(z)}$ and ${\displaystyle (z-a)^{m}f(z)}$, it is also a root of ${\displaystyle g'(z)}$ and ${\displaystyle ((z-a)^{m}f(z))'}$ and therefore ${\displaystyle \lim _{z\to a}{\frac {((z-a)^{m}f(z))'}{g'(z)}}}$ is also indeterminate. Therefore, we need to apply L'Hôpital's rule ${\displaystyle m}$ times:

${\displaystyle \lim _{z\to a}{\frac {((z-a)^{m}f(z))^{(m)}}{g^{(m)}(z)}}=\lim _{z\to a}{\frac {((z-a)^{m}f'(z)+m(z-a)^{m-1}f(z))^{(m-1)}}{g^{(m)}(z)}}=\lim _{z\to a}{\frac {((z-a)^{m}f''(z)+2m(z-a)^{m-1}f'(z)+m(m-1)(z-a)^{m-2}f(z))^{(m-2)}}{g^{(m)}(z)}}=\cdots ={\frac {m!f(a)}{g^{(m)}(a)}}}$

## Proof of binomial asymptotics

${\displaystyle {\binom {n+m-1}{n}}={\frac {(n+m-1)!}{n!(m-1)!}}={\frac {(n+1)(n+2)\cdots (n+m-1)}{(m-1)!}}\sim {\frac {n^{m-1}}{(m-1)!}}}$ as ${\displaystyle n\to \infty }$.

## Notes

1. Sedgewick, pp. 59.
2. Sedgewick, (errata), pp. 8.
3. Sedgewick, pp. 59-60.
4. Wilf 2006, pp. 185-186.
5. 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.
6. Wilf 2006, pp. 185-186.
7. Flajolet and Sedgewick 2009, pp. 231.
8. Stroud 2003, pp. 919-920.
9. This is a bit of an over-simplification. For further information, see Stroud 2003, pp. 863-867, 915 and w:Mathematical_singularity.
10. Stroud 2003, pp. 915.
11. Wilf 2006, pp. 52, 185-186.
12. Wilf 2006, pp. 50-52.
13. Biggs 2002, pp. 364-366.
14. Stroud 2001, pp. 792, v:Calculus/Limits#L'Hôpital's_Rule, w:L'Hôpital's_rule.

## References

• Biggs, Norman L. (2002). Discrete Mathematics (2nd ed.). Oxford University Press.
• Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
• Lang, Serge (1999). Complex Analysis (4th ed.). Springer Science+Business Media, LLC.
• Orloff, Jeremy. "Topic 7 Notes: Taylor and Laurent series" (PDF). Retrieved 3 October 2022.
• Sedgewick, Robert. "4. Complex Analysis, Rational and Meromorphic Asymptotics" (PDF). Retrieved 16 September 2022.
• Sedgewick, Robert. "4. Complex Analysis, Rational and Meromorphic Asymptotics (Errata)" (PDF). Retrieved 16 September 2022.
• Stroud, K. A. (2003). Advanced Engineering Mathematics (4th ed.). Palgrave Macmillan.
• Stroud, K. A. (2001). Engineering Mathematics (5th ed.). Palgrave Macmillan.
• Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.