Calculating the Secrets of Life: Contributions of the Mathematical Sciences to Molecular Biology (1995)
Chapter: Combinatorial Assemblies
Page 139
(5.27)
so that indeed Cband Zbcan be coupled closely if (and, it turns out, only if) b = o(n).
Combinatorial Assemblies
The spirit of the approximations in the preceding subsectionreplacing a dependent process with an independent onecarries over to other combinatorial structures. The first of these is the class of assemblies. Assemblies are labeled structures built as follows. The set {1,2,. . .,n} is partitioned into ak subsets of size k, for k = 1,2,. . .,n, and each subset of size k is marked as one of mk indecomposable components of size k. For example, in the case of permutations, mk = (k - 1)!, and the components of size k are the cycles on k elements. The number of structures N(a) of weight n having ai components of size i, i = 1,2,. . .,n, is therefore given by
(5.28)
and the total numberp(n) of structures of weight n is given by
(5.29)
A random structure of weight n is obtained by choosing one of the p(n) possibilities with equal probability. If Cj - Cj(n) denotes the number of components of size j, then
(5.30)
Page 140
In the case of permutations, this reduces to (5.22), because then mj / j! = 1 / j. Note that for any x > 0, the probability above is proportional to
so that by comparison with (5.22) we see that 
(C1, C2,. . .,Cn) = (Zl,Z2,. . .,Zn|T = n), where the Zi are independent Poisson random variables with means
In particular this implies that
where Rb = S1£i£b iZi. This observation reduces the calculation of a total variation distance between two processes to the calculation of a total variation distance between two random variables. We focus our attention on the class of assemblies that satisfies the logarithmic condition
(5.31)
for some k,y > 0. Among these are random permutations (for which (5.31) holds identically in i with k = y = 1), and random mappings of [n] to itself, for which 
. The study of random mappings has a long and venerable history in the combinatorics literature and is reviewed in Mutafciev (1984), Kolchin (1986), and Flajolet and Odlyzko (1990), for example.
Page 141
For the logarithmic class we may choose x = y-1, and then it is known (under an additional mild rate of convergence assumption in (5.31)) that
(5.32)
just as for the ESF. But more detailed information is available. For example, Arratia et al. (1994b) show that for fixed b,
(5.33)
The term |k- 1| reflects the similarity of the structure to an ESF with parameter k, whereas the term E[|Rb - E[Rb]|] reflects the local behavior of the structure.
The q-biased structures, those with probability proportional to q to the number of components, can also be studied in this way. In particular (5.30) holds, the Poisson-distributed Z, now having mean
The accuracy of the approximation of Cb by Zbfor the logarithmic class is still measured by (5.32) and (5.33), with k replaced by qk.
A rather weak consequence of the bounds typified by (5.32) and (5.33) is the fact that for each fixed b, (C1(n),C2(n),. . .,Cb(n)) Þ (Z1,Z2,. . .,Zb), meaning that the component counting process C converges in distribution (in R¥ ) to the independent process Z. For each n, we are comparing the combinatorial process to a single limiting process. This recovers the classical result of Goncharov (1944) showing that the cycle counts of a random permutation are asymptotically independent Poisson random variables with means 1/i. The analog for random mappings is due to Kolchin (1976).
