# 4. Complex Analysis, Rational and Meromorphic Asymptotics

## IV.1 Generating functions as analytic objects

## IV.2 Analytic functions and meromorphic functions

## IV.3 Singularities and exponential growth of coefficients

## IV.4 Closure properties and computable bounds

## IV.5 Rational and meromorphic functions

## Analytic transfer theorem for rational functions (common case)

If $h(z)$ is a rational function that is analytic at 0 and has a pole $\alpha=1/\beta$ of smallest modulus with multiplicity $M$*which is larger than the multiplicity of all other poles of smallest modulus,*then $$[z^n]h(z) \sim c\beta^nn^{M-1}\quad\hbox{where}\quad c = {1\over(M-1)!\alpha^M}\lim_{z\to\alpha} (\alpha - z)^Mh(z).$$

See Theorem IV.9 and Note IV.26 on page 256, noting errors in text listed on Errata page (sorry!).

*Example.*The number of ways to make change for $n$ cents with pennies,
nickels, dimes and quarters is
$$[z^n]{1\over(1-z)(1-z^5)(1-z^{10})(1-z^{25})}
~\sim {n^3\over 3!}{1\over 1\cdot 5 \cdot 10 \cdot 25}={n^3\over 7500}$$
because $z=1$ is a pole of multiplicity 4 and $$\lim_{z\to 1}{1-z\over 1-z^t} =
\lim_{z\to 1}{1\over 1 + z + z^2 + \ldots + z^{t-1}} = {1\over t}.$$

See Proposition IV.2 on page 258 and Slide 46 in Lecture 5.

With $h(z) = f(z)/g(z)$, another way to calculate the
constant is to use l'Hôpital's rule, with the result
$$c = M{(-\beta)^Mf(\alpha)\over g^{(M)}(\alpha)}.$$
See slide 30 in Lecture 4 or Theorem 4.1 in *Analysis of Algorithms*.

## IV.6 Localization of singularities

## IV.7 Singularities and functional equations

## IV.8 Perspective

#### Selected Exercises

## Note IV.28

*Supernecklaces.*A "supernecklace" of the 3rd type is a labelled cycle of cycles (see page 125). Enumerate all the supernecklaces of the 3rd type of size $n$ for $n$ = 1, 2, and 3. (There are 1, 2, and 7, respectively.) Then develop an asymptotic estimate of the number of supernecklaces of size $n$ by showing that $$[z^n]\ln\Bigl({1\over 1 - \ln{1\over 1-z}}\Bigr)\sim{1\over n}(1-e^{-1})^{-n}.$$

*Hint:*Take derivatives.

#### Selected Experiments

## Program IV.1

Compute the percentage of permutations having no singelton or doubleton cycles and compare with the asymptotic estimate from analytic combinatorics, for N = 10 and N = 20 .

## Program IV.2

Plot the derivative of the GF for supernecklaces of type 3 (see Note IV.28) in the style of the plots in Lecture 4. Click here for access to the Java code in the lecture.

#### Web Exercises

## IV.1

(D. Luo) Approximately how many ways are there to change $n$ cents in Canada (no pennies)?

## IV.2

(M. Moore) A "supernecklace" of the 1st type is a labelled cycle of sequences (see page 125). Enumerate all the supernecklaces of the 1st type of size $n$ for $n$ = 1, 2, and 3. (There are 1, 3, and 14, respectively.) The construction $S = CYC(SEQ_{>0}(Z))$ immediately leads to the EGF $$S(z) = \ln{1\over 1 - {z\over 1-z}} = \ln{1-z\over 1-2z}.$$ Use this to show that then number of supernecklaces of the 1st type of size $n$ is $\sim (n-1)!2^n$.*Hint:*Take derivatives.

## IV.3

Suppose that $h(z)$ is a meromorphic function with positive coefficients and that $\alpha$ is a pole of smallest modulus. The table below gives various possibilities for the modulus, multiplicity, and dominance of $\alpha$. For each row, indicate whether the order of growth of $[z^n]h(z)$ is constant, linear, quadratic, exponential, exponentially small, or none of these options.

modulus | multiplicity | dominant? |
---|---|---|

1 | 1 | yes |

1 | 1 | no |

1 | 2 | yes |

1 | 3 | yes |

1/2 | 1 | yes |

1/2 | 2 | no |

2 | 1 | yes |

## IV.4

(D. Carter) An*ultranecklace*is a cycle of supernecklaces of type 3. Give a ~-expression for the number of ultrnecklaces of size $N$.