One version of the Prime Number Theorem is that $p_n \sim n \ \ln \ n$, while by Stirling's formula $\ln(n!) \sim n \ \ln \ n$; consequently, $p_n \sim \ln(n!)$, $\rm \color{red}{\text{and } e^{-p_n} \sim \frac{1}{n!} ^{(*)}}$. Now, each side of the latter formula has a simple interpretation in the context of random permutations of $n$ elements. On the one hand, each possible outcome of a random permutation of $\langle 1,2,\dots,n \rangle$ has probability $\frac{1}{n!}$. On the other hand, the limiting probability (as $n \to\infty)$ that such a random permutation has no fixed point (i.e., that $\mathrm{perm} \langle 1,2,\dots,n \rangle$ does not match $\langle 1,2,\dots,n \rangle$ in any position) is $e^{-1}$; so, for $p_n$ independent random permutations of $\langle 1,2,\dots,n \rangle$, the probability that none of them has a fixed point is $e^{-p_n}$.

Are there "intuitive" grounds for expecting the event $E_n$ := "each of $p_n$ independent random permutations of $n$ elements has no fixed point" to have asymptotic probability $\frac1{n!}$?

$\rm \color{red}{^{(*)} \text{This is a non sequitur and is in fact false, as described in the answer and comments below.}}$

  • 4
    $\begingroup$ This isn't quite the connection you're asking about, but there is an interesting analogy between the cycle decomposition of a random permutation and the prime factorization of a random integer that might be relevant. There is a paper by Granville on the subject: dms.umontreal.ca/~andrew/PDF/Anatomy.pdf $\endgroup$ – Qiaochu Yuan Oct 18 '11 at 15:16
  • 11
    $\begingroup$ Beware: $a_n \sim b_n$ need not imply $\exp(a_n) \sim \exp(b_n)$. $\endgroup$ – GEdgar Oct 18 '11 at 15:20
  • $\begingroup$ Oops ... Back to the drawing board. (Being new to SE, I'm not sure what to do with the posted question now.) $\endgroup$ – r.e.s. Oct 18 '11 at 15:25
  • $\begingroup$ @r.e.s. Please let it stand here. The answer warns eveyone about the flaw, but it is still an interesting line of reasoning. $\endgroup$ – Phira Oct 18 '11 at 15:51
  • 2
    $\begingroup$ @r.e.s.: There's nothing wrong with the question. You posed it; someone answered it; if you agree that it was answered, you can accept the answer. There's nothing else to do about it. $\endgroup$ – joriki Oct 18 '11 at 15:54

There is a flaw in your question. From the fact that $$p_n =n\log n+n\log\log n+O(n)$$ combined with $$\log(n!)\sim n\log n+O(n)$$ we see that the asymptotic $e^{p_n}\sim n!$ is impossible. Specifically, $$\frac{e^{p_n}}{n!}=\exp(n\log\log n+O(n))=\exp(n\log\log n)\exp\left(1+O\left(\frac{1}{\log\log n}\right)\right)$$ $$=e^{n\log\log n}\left(1+O\left(\frac{1}{\log \log n}\right)\right),$$ whereas $n!\sim e^{p_n}$ is equivalent to $$\lim_{n\rightarrow \infty} \frac{e^{p_n}}{n!}=1.$$

Remark: A very useful trick to deal with an error term in the exponent is to rearrange until you have $$\exp\left(1+O(f(n))\right).$$ Assuming $f(n)$ decreases to zero, then $$\exp\left(1+O(f(n))\right)=1+O\left(f(n)\right)$$ by using the Taylor Expansion.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.