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