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