Random Permutations

December 8, 2019

Random Permutations

John Baez

Six random permutations of a 500-element 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:

François Bergeron, Gilbert Labelle, and Pierre Leroux, Introduction to the Theory of Species of Structures.

Phillipe Flajolet and Robert Sedgewick, Analytic Combinatorics.

Herbert S. Wilf, Generatingfunctionology.