# 5. Applications of Rational and Meromorphic Asymptotics

## V.1 A roadmap to rational and meromorphic asymptotics

## V.2 The supercritical sequence schema

## V.3 Regular specifications and languages

## V.4 Nested sequences, lattice paths, and continued fractions

## V.5 Paths in graphs and automata

## V.6 Transfer matrix models

## V.7 Perspective

#### Web Exercises

## V.1

Give an asymptotic expression for the number of strings that do not contain the pattern`0000000001`. Do the same for

`0101010101`.

## V.2

Consider the class of compositions of 1s, 2s, and 3s. Give asymptotic expressions for the number of objects of size*N*and the number of parts in a random object of size

*N*.

## V.3

Consider the class of triple surjections. Give asymptotic expressions for the number of objects of size*N*and the number of parts in a random object of size

*N*.

## V.4

Consider the class of alignments with no singleton cycles. Give asymptotic expressions for the number of objects of size*N*and the number of parts in a random object of size

*N*.

## V.5

An*r-surjection*is an onto mapping from [1..n] onto [1..r]. A

*surjection*is an $r$-surjection for some $r$. What is the average value of $r$ for a surjection of length $n$?

## V.6

Use analytic combinatorics to calculate a ~-approximation to the percentage of permutations having no cycles whose length is a perfect square.*Very helpful hint*: $1 + 1/4 + 1/9 + 1/16 + \ldots = \pi^2/6$.

## V.7

(A. Alag, R. Jasani) Give a ~-approximation for the average number of cycles in a random alignment that contains no singleton cycles.

#### Selected Experiments

## Program V.1

In the style of the plots in the Lecture 6, plot the GFs for the set of bitstrings having no occurrence of the pattern`0000000001`. Do the same for

`0101010101`. (See Web Exercise V.1 and Program IV.2).