Ordered cycle lengths in a random permutation

Introduction. Problems involving a random permutation are often concerned with the cycle structure of the permutation. Let tY. n be the n! permutation operators on n numbered places, and let a (X) = (aI (Q), x2 (Q), ***, ;r) ) designate the cycle class of X E. Y. 9 that is, permutation nr has xcl (Q) cycles of length 1, a2 (7r) cycles of length 2, *--. Suppose the elements of 9Yn are assigned probability 1/n! each. In a variety of problems one seeks limiting (large n) properties of random variables which depend on 7r only by way of oa (X). In the matching problem, for instance, the result limn prob la = 0 = e-' is an old one 1, p. 50. Goncharov in 2, 3 gives limiting forms for the distribution of each cj, of? j, and of the longest cycle. In 4, 5 Golomb also investigates the longest cycle. With 4n the expected length of the longest cycle, Golomb shows that la/n is monotone decreasing, and gives the numerical value 0. 62432965. . . for the limit. Answering in part a question raised by Golomb, we give a closed form for this limit (Equa! tion (14) ) ; in fact, we give in? 4 the corresponding result for the mth moment of the length of the rth longest cycle for m = 1, 2, *-- and r = 1, 2, *-, and we give the limiting distribution for the length of the rth longest cycle. In? 5 we give asymptotics for the distribution and all moments of the length of the rth shortest cycle, r = 1, 2, -*. The results and proofs are more complicated for the moments of the rth shortest cycle than for the rth longest. Our methods are straightforward: we set up generating functions, get leading terms in closed form, and use Tauberian methods to recover the asymptotic dependence on n. The Tauberian side conditions needed are based on the combinatorial arguments of? 6. 2. A model. For given n the distribution of a is obtained by dividing the number of permutations in class a by n!: Pal = al, M2 = a2,. . an = an (1) ~~~~~~~~n (11y, a n =15