Random Permutations (Part 0)

## Random Permutations (Part 0)

#### John Baez

I'm falling in love with random permutations. There's something both simple and fairly deep about them. I like to visualize a random permutation as a "gas of cycles", governed by the laws of statistical mechanics. I haven't gotten very with this analogy yet. But I'm learning a lot of fun stuff.

Here's one of the many cute facts about random permutations — not every easy to prove, but cute.

Let $$a_n$$ be the average length of the longest cycle in a permutation, averaged over all permutations of an $$n$$-element set. Then $$a_n$$ is asymptotically equal to $$\lambda n$$ where

$\lambda \approx 0.6243299885 \dots$

is called the Golomb–Dickman constant. There's a cool formula for this constant: $\lambda = \int_0^1 e^{\mathrm{Li}(x)} dx \; \; \textrm{where} \; \; \mathrm{Li}(x) = \int_0^x \frac{dt}{\ln t}$ But nobody has been able to prove that it's irrational!

The Golomb–Dickman constant also shows up in number theory... in a very similar way! If you randomly choose a huge $$n$$-digit integer, the average number of digits of its largest prime factor is asymptotic to $$\lambda n$$.

So, there's a connection between prime factorizations and random permutations! And this fact is both simpler and more interesting to me than the Golomb–Dickman constant. You can read more about this here:

The Golomb–Dickman constant is a kind of relative of Euler's constant, though there's no known formula expressing one in terms of the other.

Here's another appearance of this constant. Say you randomly choose a function from a huge $$n$$-element set to itself. Then the average length of its longest periodic orbit is asymptotic to

$\lambda \; \sqrt{\frac{\pi n}{2}}$

Next time I'll start explaining proofs of some other facts about random permutations — facts that are easier to prove!