# The asymptotic behaviour for the probability that a random permutation in $S_n$ has order $2$.

Let $T_n$ be the number of elements of $S_n$ with order $1$ or $2$. It is well known that:

$$T_n = \sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{2k}(2k-1)!! = \frac{d^n}{dx^n}\left.\exp\left(x+\frac{x^2}{2}\right)\right|_{x=0}$$

and, if we call $D_n = \frac{T_n}{n!},$ $$D_n = \frac{1}{n}\left(D_{n-1}+D_{n-2}\right).$$

My question is: what is the asymptotic behaviour of $D_n$ as $n$ goes to infinity?

Is it possible to apply some saddle-point method in this case?

-
Your sequence $T_n$ is described here: oeis.org/A000085. – Yury Nov 27 '12 at 6:14

This is indeed amenable to the saddle-point method, and is analysed in detail in Example VIII.5 on page 558 of Analytic Combinatorics. $$D_n=\frac{e^{-1/4}}{2\sqrt{\pi n}}n^{-n/2}e^{n/2+\sqrt{n}}\left(1+O\left(\frac{1}{n^{1/5}}\right)\right).$$ This result was first given by Knuth in The Art of Computer Programming vol. 3.
Also writeable as $D_n=\sum_{k=0}^{\lfloor\frac n2\rfloor} \frac{1}{k!(n-2k)!2^{k}}$. For big $n$ this is dominated by $\frac kn\approx \alpha=2-\sqrt 3$ (i.e., when $\frac{2k}{(2k-1)^2}\approx1$). Using Stirling and $1-2\alpha=\alpha\sqrt 3$, $(1+\sqrt 3)\alpha = \sqrt 3-1=:\beta$, then $k!(n-2k)!2^k\approx (\alpha n)^{\alpha n}e^{-\alpha n}\sqrt{2\pi\alpha n}\cdot (\sqrt 3\alpha n)^{\sqrt 3 \alpha n}e^{-\sqrt 3\alpha n}\sqrt{2\pi\sqrt 3\alpha n}\cdot 2^{\alpha n}=2\pi(\sqrt3)^{\alpha n+\frac12}(\alpha n)^{\beta n+1}e^{-\beta n}$.
Was this written too hastily? I seem to find the mode when $2k\approx n-\sqrt{n}$. – Did Oct 25 '12 at 6:44