Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Your sequence $T_n$ is described here: – Yury Nov 27 '12 at 6:14
up vote 3 down vote accepted

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|cite|improve this answer

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|cite|improve this answer
Was this written too hastily? I seem to find the mode when $2k\approx n-\sqrt{n}$. – Did Oct 25 '12 at 6:44

Your Answer


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.