Analytic Combinatorics/Meromorphic Functions

This article explains how to estimate the coefficients of meromorphic generating functions which have only one dominant singularity.

Theorem due to Sedgewick^[1].

• If ${\displaystyle h(z)={\frac {f(z)}{g(z)}}}$ is a meromorphic function
• which has only one pole, ${\displaystyle a}$, 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 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 }$

• this Laurent expansion can be estimated by its principle part^[6]:

${\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 }$.

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}}$.

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.

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.

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}}}$.

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|}$.

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

${\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'|>|a|}$ then as ${\displaystyle n}$ gets large ${\displaystyle \left({\frac {1}{|a'|}}\right)^{n}}$ will be much smaller than ${\displaystyle \left({\frac {1}{|a|}}\right)^{n}}$ and, therefore, ${\displaystyle PP(h,a)}$ is a good enough approximation of ${\displaystyle h(z)}$.

However, if ${\displaystyle |a'|=|a|}$ then the behaviour of the coefficients is more complicated.

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}}})}$.

${\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].

${\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)}}}$

${\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 }$.

• 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.