Limit Theorems for Combinatorial Structures via Discrete Process Approximations
Richard Arratia, Simon Tavaré · Random Structures and Algorithms · 1992
Abstract Discrete functional limit theorems, which give independent process approximations for the joint distribution of the component structure of combinatorial objects such as permutations and mappings, have recently become available. In this article, we demonstrate the power of these theorems to provide elementary proofs of a variety of new and old limit theorems, including results previously proved by complicated analytical methods. Among the examples we treat are Brownian motion limit theorems for the cycle counts of a random permutation or the component counts of a random mapping, a Poisson limit law for the core of a random mapping, a generalization of the Erdös–Turán Law for the log‐order of a random permutation and the smallest component size of a random permutation, approximations to the joint laws of the smallest cycle sizes of a random mapping, and a limit distribution for the difference between the total number of cycles and the number of distinct cycle sizes in a random permutation.