How to estimate $\sum_{k=0}^{n}\frac{1}{k!} {n \choose k}$

Question

I want to estimate this summation

$$\sum_{k=0}^{n}\frac{1}{k!} {n \choose k}$$

It seems to be about $\sqrt{n}$

how can i prove that?

---

It rises from the problem of calculating the expectation value of longest increasing subsequence of a given sequence. if some one has another idea for solving the original problem i will be pleased for sharing.

Thanks...

Answer 1

Your sum is equal to $L_n(-1)-1$, where $L_n$ is a Laguerre Polynomial (see specifically the closed form given in the link).

The same page also provides asymptotics (with $\alpha=0$ for generalized Laguerre):

$$L_n(-x)\approx \frac{(n+1)^{-1/4}}{2\sqrt{\pi}}\frac{e^{-x/2}}{x^{1/4}}e^{2\sqrt{x(n+1)}}\left(1+O(1/\sqrt{n+1})\right),$$

so just plug in $x=1$. It looks like the growth rate will be something like:

$$\frac{e^{\sqrt{n}}}{n^{1/4}}.$$