Sankhyā : The Indian Journal of Statistics 1997, Volume 59, Series A, Pt. 1, pp. 133-137

THE MOMENTS OF THE NUMBER OF CYCLES OF

A RANDOM PERMUTATION BY SIMPLE ENUMERATION

By T. LENGYEL Occidental College, Los Angeles

SUMMARY. We present a new proof for the Poisson limit distribution of the number of fixed points of a random permutation. Despite the combinatorial nature of the proof, it does not involve the use of inclusion-exclusion principle, cycle representation of permutations, number of derangements, rewriting formulas for the distribution of the fix points, generating functions, or transformation formulas between moments. The proof is elementary in terms of enumeration and based on the notion of Stirling numbers. It requires some familiarity with the moment generating function of the Poisson distribution and the Fréchet-Shohat moment convergence theorem. The method is extended to the distribution of the number of k-cycles of an n-element set, for k ≤ n.

1. Introduction

Let X_{n,r} denote the number of r-cycles of a random permutation over an n-element set [n] = {1, 2, …, n}. We use the convenient X_{n} = X_{n,1} notation for the number of fixed points. Let p_{n}(k) denote the probability that a random permutation over [n], for short a random n-permutation, has k fixed points, i.e., p_{n}(k) = P (X_{n} = k). We find the k-th moments M_{k}(n) = E(X_{n}^{k}) and M_{k}(n, r) = E(X_{n,r}^{k}) without using any inclusion-exclusion, inversion or moment transformation formula or determining the related probabilities.

The convergence of the distribution of X_{n} to the Poisson distribution is well known. The limiting distribution can be determined by using formulas for p_{n}(k). We take a different approach and find the limit distributions (Corollary) based on a moment convergence theorem by calculating the moments (Theorems 1 and 2). Although we might encounter difficulties for other distributions, in this case we can give a simple interpretation of the moments without determining the explicit probabilities.

Paper received. May 1993. revised June 1996. AMS (1980) subject classifications. 60C05, 05A05, 60E10, 05A19. Key words and phrases. Random permutations, moments, combinational probability.

We note that Takács (1991) has recently proved a general convergence theorem based on the binomial moments which in addition yields an explicit formula for the limit distribution. We will use neither binomial nor factorial moments.

In this paper S(n, k) denotes the Stirling number of the second kind, i.e., the number of partitions of n distinct elements into k non-empty subsets and (x)_{k} stands for x(x − 1) … (x − k + 1) where k = 1, 2, … The Bell number, ϖ(n), is defined as the number of all partitions of [n], i.e., ϖ(n) = ∑_{k=1}^{n} S(n, k).

2. The number of fixed points and k-cycles of a random permutation

The problem of analyzing p_{n}(k) and the expected value of the number of fixed points of a random n-permutation is probably originated in card games. We count the matches when the cards of two well-shuffled decks are matched against each other. The first solution goes back to Montmort who found a recurrence relation for the number of matches in 1708. The problem has been generalized in many ways and counting unrestricted and restricted permutations of an n-element set has been a popular area of research (e.g., Penrice (1991) and Takács (1981)).

The probability p_{n}(k) is usually determined by the inclusion-exclusion principle (cf. Feller (1968), Graham et al. (1988), and Wilf (1990)). Notice that p_{n}(n − 1) = 0. It also follows that p_{n}(0) = ∑_{i=0}^{n}(−1)^{i} \frac{1}{i!} = e^{−1} + O(1/n!) and p_{n}(k) = \frac{1}{k!} ∑_{i=0}^{n−k}(−1)^{i} \frac{1}{i!}, which yields the asymptotic formula p_{n}(k) = \frac{1}{ek!} + O(\frac{1}{(n−k)!}), for every fixed k (see e.g., Feller (1968)). The asymptotic behavior of p_{n}(k) can be derived by the method of generating functions (cf. Wilf (1990)) too. Roughly speaking, p_{n}(k) conforms to the Poisson law with parameter 1 as n tends to ∞. Similar results hold for the distribution of X_{n,r}. We give an alternative proof of these facts based on the moments.

Observe that the probabilities are nearly independent of n. It turns out that for n ≥ 2, M_{1}(n) = E(X_{n}) = 1 and M_{2}(n) = E(X_{n}^{2}) = 2 do not depend on n. In general, one can calculate M_{k}(n) by

Theorem 1. The moments M_{k}(n) = E(X_{n}^{k}) of the number of fixed points of a random n-permutation are

M_{k}(n) = \{ \begin{matrix}ϖ(k), & if & k ≤ n \\ ∑_{i=1}^{n} S(k, i) & if & k > n. \end{matrix}

Note that for every n, the first n moments of X_{n} do not depend on n. We set M_{0}(n) = 1(n ≥ 1).

Proof. Let Y_{i} be the indicator random variable of the event that element i is a fixed point of the random n-permutation, i.e.,

Y_{i} = \{ \begin{matrix}1, & if element i is a fixed point, \\ 0, & otherwise. \end{matrix}

Clearly, the random variables Y_{i} are identically distributed though they are not independent. For the number of fixed points X_{n}, we get X_{n} = ∑_{i=1}^{n} Y_{i}. We evaluate M_{k}(n) = E(X_{n}^{k}) by expanding the right hand side of this equation using the multinomial expansion. That is,

M_{k}(n) = E ((Y_{1} + Y_{2} + … + Y_{n})^{k}) = ∑_{N_{n}} ( \begin{matrix}k \\ i_{1} … i_{n} \end{matrix} ) E(Y_{1}^{i_{1}}Y_{2}^{i_{2}} … Y_{n}^{i_{n}})

where the summation extends over the set N_{n} of n-tuples (i_{1}, i_{2}, …, i_{n}) with non-negative integer coordinates provided ∑_{j=1}^{n} i_{j} = k.

Let l = l(i_{1}, i_{2}, …, i_{n}) denote the number of positive exponents in Y_{1}^{i_{1}}Y_{2}^{i_{2}} … Y_{n}^{i_{n}}, i.e., l = |{j|i_{j} ≥ 1}|. Clearly, 1 ≤ l ≤ min{k, n}. Notice that Y_{i}^{c} = Y_{i} if c ≠ 0. One can easily see that Y_{i}^{i_{1}}Y_{2}^{i_{2}} … Y_{n}^{i_{n}} and Y_{1}Y_{2} … Y_{l(i_{1},i_{2},...,i_{n})} are identically distributed. There are \binom{n}{l} ways to choose the l variables with a given set of positive exponents. For Y_{1}Y_{2} … Y_{l} = 1 if and only if the n-permutation has the first l elements of [n] as fixed points, thus E(Y_{1}Y_{2} … Y_{l}) = \frac{(n−l)!}{n!}. Let N_{l}^{+} denote the set of l-tuples (i_{1}, i_{2}, …, i_{l}) such that i_{j} ≥ 1, for all j, 1 ≤ j ≤ l, and ∑_{j=1}^{l} i_{j} = k. It follows that

M_{k}(n) = ∑_{l=1}^{min\{k,n\}} ∑_{N_{l}^{+}} ( \begin{matrix}k \\ i_{1} … i_{l} \end{matrix} ) ( \begin{matrix}n \\ l \end{matrix} ) \frac{(n − l)!}{n!} = ∑_{l=1}^{min\{k,n\}} ∑_{N_{l}^{+}} ( \begin{matrix}k \\ i_{1} … i_{l} \end{matrix} ) \frac{1}{l!}.

Now observe that

∑_{N_{l}^{+}} ( \begin{matrix}k \\ i_{1} … i_{l} \end{matrix} ) = S(k, l)l!

for the number of partitions of a k-element set into l non-empty blocks is counted on both sides. The order of the blocks is taken into account but not the order of the elements inside the blocks. We find that M_{k}(n) = ∑_{l=1}^{min{k,n}} S(k, l). The proof is now complete.

Remark. The previous statement can be derived by using factorial moments for expressing M_{k}(n) = E(X_{n}^{k}), k ≥ 1. In fact, the transformation formula between central and factorial moments, X^{k} = ∑_{l=1}^{k} S(k, l)(X)_{l}, becomes E(X^{k}) = ∑_{l=1}^{k} S(k, l)E((X)_{l}) = ∑_{l=1}^{min{k,n}} S(k, l) after taking the expected values. The proof of the formula and the calculation of E((X)_{l}), however, are usually based on the combinatorial theory of the Stirling numbers of the second kind and the number of derangements. Our proof completely avoided this approach. Nonetheless, the identity x^{k} = ∑_{l=1}^{k} S(k, l)(x)_{l}, k ≥ 1, follows easily when the moment enumeration method is applied to binomially distributed random variables.

We can generalize the previous theorem and obtain

Theorem 2. The moments M_{k}(n, r) = E(X_{n,r}^{k}) of the number of r-cycles of a random n-permutation are

M_{k}(n, r) = \{ \begin{matrix}∑_{i=1}^{k} S(k, i)/r^{i}, & if & k ≤ [n/r] \\ ∑_{i=1}^{[n/r]} S(k, i)/r^{i}, & if & k > [n/r]. \end{matrix}

We note that the k-th moment of the Poisson distribution with parameter λ = 1/r is ∑_{i=1}^{k} S(k, i)/r^{i}. Theorem 2 and the Fréchet-Shohat moment convergence theorem (see e.g., Moran (1968)) implies

Corollary. The number of r-cycles of a random n-permutation has Poisson limit distribution with parameter 1/r.

Proof of Theorem 2. The proof is based on the revised definition of the indicator variables Y_{i}. We set N = \binom{n}{r} and define Y_{i}, i = 1, 2, …, N, as the indicator variable of the event that the i-th element in the list of r-element subsets of [n] forms an r-cycle of the random n-permutation. That is,

Y_{i} = \{ \begin{matrix}1, & if the i-th r-element subset of [n] is an r-cycle, \\ 0, & otherwise. \end{matrix}

Let l = l(i_{1}, i_{2}, …, i_{n}) denote the number of positive exponents in Y_{1}^{i_{1}}Y_{2}^{i_{2}} … Y_{N}^{i_{N}}. Incidentally, Y_{1}^{i_{1}}Y_{2}^{i_{2}} … Y_{n}^{i_{N}} is zero or one, and it is one if and only if the corresponding l r-element subsets form disjoint r-cycles of the permutation. Provided the subsets are disjoint, there are ((r−1)!)^{l}(n−lr)! ways of forming the required r-cycles and completing the n-permutation. We can select the l disjoint subsets

in ( \begin{matrix}n \\ r … r \end{matrix} ) /l! ways (with l copies of r under n), and there are S(k, l)l! ways of

making l-tuples with positive coordinates of sum k. In other words, the multinomial expansion of E ((Y_{1} + Y_{2} + … + Y_{N})^{k}) has S(k, l)l! terms Y_{1}^{i_{1}}Y_{2}^{i_{2}} … Y_{N}^{i_{N}}, with l positive exponents, each contributing

( \begin{matrix}n \\ r … r \end{matrix} ) \frac{1}{l!} \frac{((r − 1)!)^{l}(n − lr)!}{n!} = \frac{1}{r^{l}l!}

to M_{k}(n, r). Summation on l, 1 ≤ l ≤ min{k, [n/r]}, yields the identity for M_{k}(n, r). the number of cycles by simple enumeration 137

References

Feller, W (1968). An Introduction to Probability Theory and Its Applications, vol. I, Wiley, 3rd edition.

Graham, R.L., Knuth, D.E. and Patashnik, O. (1989). Concrete Mathematics, Addison-Wesley, Reading, MA.

Moran, P.A.P. (1968). An Introduction to Probability Theory, Oxford.

Penrice, S.G. (1991). Derangements, permanents, and Christmas presents, Amer. Math. Monthly, 94, 617-620.

Takács, L. (1981). On the “Problème des ménages”, Discrete Mathematics, 36, 289-297.

− − −− (1991). A moment convergence theorem, Amer. Math. Monthly, 94, 742-746.

Wilf, H.S. (1990). generatingfunctionology, Academic Press, Boston.

Department of Mathematics Occidental College 1600 Campus Road Los Angeles CA 90041 U.S.A.