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:
© 2019 John Baez
baez@math.removethis.ucr.andthis.edu
home