|
|
|
|
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!
You can also read comments on the n-Category Café, and make your own comments or ask questions there!
|
|
|
|