# 6. Singularity Analysis of Generating Functions

## VI.1 A glimpse of basic singularity analysis theory

## VI.2 Coefficient asymptotics for the standard scale

## VI.3 Transfers

## VI.4 The process of singularity analysis

## VI.5 Multiple singularities

## VI.6 Intermezzo: functions amenable to singularity analysis

## VI.7 Inverse functions

## VI.8 Polylogarithms

## VI.9 Functional composition

## VI.10 Closure properties

## VI.11 Tauberian theory and Darboux’s method

## VI.12 Perspective

#### Web Exercises

## VI.1

Use the standard function scale to directly derive an asymptotic expression for the number of strings in this following CFG: S = E + U×Z×S + D×Z×S, U = Z + U×U×Z, D = Z + D×D×Z.

## VI.2

Give an asymptotic expression for the number of rooted ordered trees for which every node has 0, 2, or 3 children. How many bits are necessary to represent such a tree?

## VI.3

(D. Carter) A*rainbow tree*is a rooted ordered tree where each node is one of four colors, with the rules that each node differs in color from its parent and can only have children which all differ in color from each other. (Note that no node can have more than 3 children.) Give a ~-expression for the number of rainbow trees with $N$ nodes.

#### Selected Experiments

## Program VI.1

In the style of the plots in Lecture 6, do $r$- and $\theta$-plots of $1/\Gamma(z)$ in the unit square of size 10 centered at the origin. Click here for access to the Java code used for the lecture.