# 4.   Complex Analysis, Rational and Meromorphic Asymptotics

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

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

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

## 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?
11yes
11no
12yes
13yes
1/21yes
1/22no
21yes

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

## IV.5

(A. Yan) Give a ~-approximation for $$[z^N]{1\over(1-z)(1-2z)(1-3z)\ldots(1-tz)}$$.