On random mapping patterns (Q788742): Difference between revisions

A functional digraph is one in which every vertex has outdegree 1; these are cryptomorphs of the functions from a set to itself. This paper concerns several quantities related to the collection of all unlabeled (i.e. isomorphism classes of) functional digraphs on n points, which we here call UFD(n)'s. The structure of UFD's is quite simple: each connected component of a UFD consists of a directed cycle and a collection of rooted trees whose roots are vertices of the cycle and whose edges are directed toward the roots. Earlier investigators have thereby made connections between the generating function P(x) for UFD(n)'s and T(x) for unlabeled rooted trees on n points. In this paper the authors obtain generating functions and approximate asymptotic values for five other quantities: the number of connected UFD(n)'s; the expected length of the unique cycle in a random connected UFD(n); the number of all UFD(n)'s; the expected number of points in cycles in a random UFD(n); and the expected number of connected components of a random UFD(n). The five main theorems of the paper obtain the generating functions in terms of T(x), primarily using Pólya theory. The asymptotic values are obtained as corollaries, through a lemma essentially due to Darboux; they use earlier work of Otter, who found that T(x) has radius of convergence \(\rho =.3383..\). and has an expansion in powers of \(z=/(\rho -x)\) that begins 1-bz where \(b=2.6811..\).. The asymptotic values are given in terms of \(\rho\) and b.