7. Applications of Singularity Analysis
VII.1 A roadmap to singularity analysis asymptotics
VII.2 Sets and the exp–log schema
VII.3 Simple varieties of trees and inverse functions
VII.4 Tree-like structures and implicit functions
VII.5 Unlabelled non-plane trees and P´olya operators
VII.6 Irreducible context-free structures
VII.7 The general analysis of algebraic functions
VII.8 Combinatorial applications of algebraic functions
VII.9 Ordinary differential equations and systems
VII.10 Singularity analysis and probability distributions
VII.11 Perspective
Web Exercises
VII.1
Use the tree-like schema to develop an asymptotic expression for the number of bracketings with $N$ leaves (see Example I.15 on page 69 and Note VII.19 on page 474)
VII.2
Develop an asymptotic expression for the number of rooted ordered trees of size $N$ with no nodes having a single child.
VII.3
For each of the following combinatorial constructions, give the appropriate schema for developing asymptotic enumeration results (simple variety of trees, exp-log, or implicit tree-like class). When two apply, pick the simpler one. $A = Z\times SEQ(A)$, $A = Z + SEQ_{>1}(A)$, $A = SET(CYC(Z))$, $B = Z\times (1+B)^4$, $A = Z\star SET(A)$, $A = Z + SET_{>1}(A)$, $A = SET(CYC_{>1}(Z))$.
VII.4
(A. Ding) Show that the proportion of the 2-regular simple graphs on $N$ vertices whose cycles are all of length greater than $r$ is about $e^{3/4}/\sqrt{r}$ for large $r$.
Selected Experiments
Program VII.1
Do r- and θ-plots of the GF for bracketings (see Web Exercise VII.1).