Random Permutations
December 8, 2019
Random Permutations
John Baez
Six random permutations of a 500element set, where
circle areas are drawn in proportion to cycle lengths.
From Analytic Combinatorics by Flajolet and Sedgewick.
Say you randomly choose one of the \(n!\) permutations of a huge
\(n\)element set. What's it like, typically? This is actually many
questions in one. Answering these questions uses a fascinating mix of
elementary techniques, generating functions, and complex analysis.
And the answers are often beautifully simple!

Part 0 — What's the average length
of the longest cycle in a random permutation of an \(n\)element set?

Part 1 — What is the probability that a randomly chosen permutation of an \(n\)element set has exactly \(k\) fixed points?

Part 2 — What is the probability that the shortest cycle in a randomly chosen permutation of an \(n\)element set has length greater than \(k\)?

Part 3 — A large collection of questions about random permutations, with answers.

Part 4 — What is the probability that a randomly chosen permutation of an \(n\)element set has a cycle of length greater than \(n/2\)?

Part 5 — What is the average length of a cycle in a randomly chosen permutation of an \(n\)element set?

Part 6 — What expected number of cycles of length \(k\) in a randomly chosen permutation of an \(n\)element set?

Part 7 — How is the distribution of the number of cycles of length \(k\) in a random permutation related to a Poisson distribution?

Part 8 — What's the \(n\)th moment of a Poisson distribution?
My own arguments emphasize the use of combinatorial
species and their generating functions, so it will help if you know
a bit about those. These books are helpful:
© 2019 John Baez
baez@math.removethis.ucr.andthis.edu
home