Abstract:
There are many combinatorial structures which can be regarded as complexes of certain basic
blocks. Familiar examples are involutions, finite graphs, and Stirling numbers of the first and
second kind. Generating functions for these complexes have special forms relating the number
of basic blocks to the number of complexes. Previous results on asymptotic enumeration have
yielded implicit formulae for the mean and variance of the counts of blocks, together with Gaussian
approximations with these parameters. We will provide explicit formulae for these basic quantities,
together with large deviation estimates for decay rates from the mean. As a result we obtain laws of
large numbers and, under certain convexity conditions, a new approach to Gaussian approximations
previously obtained by more cumbersome analysis.
In regard to applications, we will provide a new connection between these combinatorial structures
and a class of self-similar trees. Extensive data analysis of naturally occurring river networks has
been shown by hydrologists to be nicely modeled by this class of self-similar trees. Through this
connection, we will obtain new results on the number of paths of various Horton orders.
