Random Permutations

January 11, 2020

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!

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