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


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)


Develop an asymptotic expression for the number of rooted ordered trees of size $N$ with no nodes having a single child.


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


(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).