4
$\begingroup$

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?

  • 1
    Your sequence $T_n$ is described here: http://oeis.org/A000085.2012-11-27

2 Answers 2

4

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.

0

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}$.

  • 3
    Was this written too hastily? I seem to find the mode when $2k\approx n-\sqrt{n}$.2012-10-25