I am interested any approximation that may be available for the following expression:
$$ {\left(2n\right)}!\sum_{k=0}^{n}\frac {1} {2^k \; k! \; \left(2n-2k\right)!} $$ ... which can be expressed more tersely as: $$ \sum_{k=0}^{n}\frac {{^{2n}\mathrm{C}_{2k}}\;{^{2k}\mathrm{P}_k}} {2^k} $$ ... or alternatively: $$ \sum_{k=0}^{n}\frac {{^{2n}\mathrm{P}_{2k}}} {2^k\;k!} $$
... and which actually is the number of involution permutations of $\color{red}{2n}$ objects. I'm interested in moderately large $n$, say $2^{32}$ or more ...
This question originated from trying to figure out the probability that a randomly picked permutation is an involution. I could track it down to $\sum_{k=0}^{n}\frac {1} {2^k \; k! \; \left(2n-2k\right)!}$ for $2n$ objects, but I was trying to get a feel of how this probability changes as $n$ increases.
I thought of using Stirling's approximation, but I'm not too sure that it won't be misleading given that there are factorials of low values in here as well -- and there is a summation.
Can anyone help? Thanks...
OK, I could find the answer myself ...
It seems what I asked has an actual name -- the number of involutions for $n$ objects is called the Telephone Number $T\left(n\right)$.
For my question, the number of objects is $2n$, and the answer can be approximated as follows: $$ \sum_{k=0}^{n}\frac {{^{2n}\mathrm{P}_{2k}}} {2^k\;k!} = T\left(2n\right) \sim \left(\frac {2n} {e} \right)^{n} \frac {e^{\sqrt{2n}}}{\sqrt{2}\sqrt[4]{e}} $$ ... which means that for large $n$, the probability that a randomly chosen permutation of $2n$ objects is an involution is approximately: $$ \frac {1}{2\sqrt{2\pi}\sqrt[4]{e}}\left(\frac {e} {2n} \right)^{n} \frac {e^{\sqrt{2n}}}{\sqrt{n}} $$ Cheers ...