Let be a natural number, and let be a permutation of , drawn uniformly at random. Using the cycle decomposition, one can view as the disjoint union of cycles of varying lengths (from to ). For each , let denote the number of cycles of of length ; thus the are natural number-valued random variables with the constraint

We let be the number of cycles (of arbitrary length); this is another natural number-valued random variable, of size at most .

I recently had need to understand the distribution of the random variables and . As it turns out this is an extremely classical subject, but as an exercise I worked out what I needed using a quite tedious computation involving generating functions that I will not reproduce here. But the resulting identities I got were so nice, that they strongly suggested the existence of elementary bijective (or “double counting”) proofs, in which the identities are proven with a minimum of computation, by interpreting each side of the identity as the cardinality (or probability) of the same quantity (or event), viewed in two different ways. I then found these bijective proofs, which I found to be rather cute; again, these are all extremely classical (closely related, for instance, to Stirling numbers of the first kind), but I thought some readers might be interested in trying to find these proofs themselves as an exercise (and I also wanted a place to write the identities down so I could retrieve them later), so I have listed the identities I found below.

- For any , one has . In particular, .
- More generally, for any and with , one has .
- More generally still, for any and with , one has
- In particular, we have
*Cauchy’s formula*: if , then the probability that for all is precisely . (This in particular leads to a reasonably tractable formula for the joint generating function of the , which is what I initially used to compute everything that I needed, before finding the slicker bijective proofs.)
- For fixed , converges in distribution as to the Poisson distribution of intensity .
- More generally, for fixed , converge in joint distribution to independent Poisson distributions of intensity respectively. (A more precise version of this claim can be found in this paper of Arratia and Tavaré.)
- One has .
- More generally, one has for all natural numbers .

### Like this:

Like Loading...

## 23 comments

Comments feed for this article

23 November, 2011 at 9:02 am

Greg MartinTerry – are the distributions of the lengths of the longest cycle and shortest cycle also known?

23 November, 2011 at 9:24 am

Terence TaoThis paper of Lloyd and Shepp seems to answer such questions fairly definitively, though the answers are somewhat messy.

23 November, 2011 at 9:15 am

Qiaochu YuanFor what it’s worth, the joint generating function of the can be computed using Polya’s enumeration theorem, and it also has an elegant explanation in terms of combinatorial species (see my blog posts here and here for details).

23 November, 2011 at 9:39 am

AnonymousTypo in the first paragraph. ‘brandom’ should be ‘random’.

[Corrected, thanks – T.]24 November, 2011 at 5:24 am

Ben GreenThere is a play (!) on this kind of thing by our friend Andrew Granville and his sister.

http://www.maa.org/mathtourist/mathtourist_01_06_10.html

I recall the accompanying music, which was in 29 time, making me feel rather queasy.

25 November, 2011 at 2:27 pm

Greg Martin29 time?

27 November, 2011 at 3:25 pm

Ben GreenYes, as in 29 beats to the bar. So far as I recall.

26 November, 2011 at 10:04 am

Emmanuel KowalskiThe play was supposed to come out as a comics, but I don’t know what happened to that project…

More mathematically, the book of Arratia, Barbour and Tavaré, “Logarithmic combinatorial structures” (see http://www.ems-ph.org/books/book.php?proj_nr=15 ) contains many generalizations, treated in a uniform manner.

12 August, 2019 at 10:38 am

Jay BederThe graphic novel has come out: Prime Suspects, by Andrew Granville and Jennifer Granville, with illustrations by Robert J. Lewis, Princeton U. Press. There are extensive endnotes by A Granville and others. Granville mentions the log N result, though without any explanation. (BTW, Tao, Green and Ziegler are among the characters in the novel.)

28 November, 2011 at 4:19 am

Lam. S.Flajolet and Knuth studied a similar problem in the graph theory context:

http://hal.inria.fr/docs/00/07/56/66/PDF/RR-0888.pdf

28 November, 2011 at 9:00 pm

A central limit theorem for the determinant of a Wigner matrix « What’s new[…] complicated (and uses facts about the distribution of cycles in random permutations, mentioned in this previous post), but one can compute that is comparable to for GUE and for GOE. (The discrepancy here comes […]

30 November, 2011 at 3:50 am

kateLove your blog. Hardcore math I see.

3 December, 2011 at 11:03 am

Slipper.MysteryOne word puzzle that employs a property of random permutations, specifically the (relatively low) probability of large cycles, is the 100 prisoners. This wikipedia entry (not among those you’ve linked) contains other useful identities.

See also

condemned prisoners from someone who liked your reprise of the blue-eyed islanders.

The problem also shows up in this

tribute to Martin Gardner.

6 December, 2011 at 8:15 am

john mangualI wonder what application you have in mind. There are lots of permutation group actions whose orbit structure we might be interested in.

7 January, 2012 at 11:51 pm

Manjunath KrishnapurThe chinese restaurant construction of a uniform random permutation probably yields all these in the cleanest way – for example, the number of cycles has the same distribution as a sum of independent Bernoullis with parameters 1, 1/2, 1/ 3,…,1/n.

26 December, 2012 at 7:28 am

Vineet GeorgeI have done extensive research on combination and permutation and found consistent and uniform result. This result which I have found is written on a book known as Junction (an art of counting combination and permutation). To view one of the result of my research work then log on to the site https://sites.google.com/site/junctionslpresentation/home

also see: https://sites.google.com/site/junctionslpresentation/proof-for-advance-permutation

21 September, 2013 at 5:07 pm

The Poisson-Dirichlet process, and large prime factors of a random number | What's new[…] Again, we prove this proposition below the fold. Now we turn to the second way (a topic, incidentally, that was briefly touched upon in this previous blog post): […]

9 August, 2014 at 10:59 pm

Sungjin KimWhile I prepare for TA session for probability class, I found that the first one has a probabilistic proof:

Let be the event that is contained in a -cycle. .

Then where is the indicator function.

follows from combinatorial counting argument.

17 September, 2018 at 4:01 am

AnonymousWhy is P(A_i) = 1/n?

26 March, 2019 at 2:53 pm

AnonymousFor a permutation, you can rearrange its cycles, such that each cycle has its minimal at the end, and the minimal elements of the cycles are in increasing order.

For example, the permutation (125)(37) (in S_7) should be written as (251)(73)(4)(6).

Note that you can read that expression without the parentheses (i.e. the only way to get the order 2517346 is (251)(73)(4)(6) ), in the following way: the first cycle should end at “1”. the second cycle should end at the minimal element after the first cycle, and so on.

Hence, we have a bijection between permutations and orders of the numbers 1…n, so you can choose an uniform order.

But now, the length of the cycle of 1 is k, iff 1 is in the kth place in our order, and the probability for that is clearly 1/n, so P(A_1)=1/n . (and the same is true for any i)

15 July, 2015 at 2:44 pm

Cycles of a random permutation, and irreducible factors of a random polynomial | What's new[…] (Prime number theorem for permutations) A randomly selected permutation of will be a cycle with probability exactly . (This was noted in this previous blog post.) […]

28 June, 2016 at 7:01 pm

Sungjin KimI think #8 holds in general for complex z as an application of Stirling number of first kind.

13 April, 2017 at 5:36 pm

Counting objects up to isomorphism: groupoid cardinality | What's new[…] a cardinality that converges in distribution to the Poisson distribution of rate (as discussed in this previous post), thus we see that the fixed points of a large random permutation asymptotically are distributed […]