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