Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Your sequence $T_n$ is described here: oeis.org/A000085. –  Yury Nov 27 '12 at 6:14
add comment

2 Answers

up vote 3 down vote accepted
+50

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.

share|improve this answer
add comment

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

share|improve this answer
3  
Was this written too hastily? I seem to find the mode when $2k\approx n-\sqrt{n}$. –  Did Oct 25 '12 at 6:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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