Does $\sum_{k=0}^{k=n} {n \choose k} k!$ have a closed form for integers $k,n$?

Question

While doing research in computer system, I came across the following summation: $$S_n = \sum_{k=0}^{n} {n \choose k} k! = \sum_{k=0}^{n} \frac{n!}{(n-k)!}$$ where both $n$ and $k$ are integers.

$S_n$ has an intuitive meaning: Suppose we have $n$ distinct numbers. Each time we choose $k$ numbers and permute them. What is the total number of different permutations?

Though I only need the value of $S_2 = 5$ and $S_3 = 16$, I am interesting in its general form. I have tried myself and googled with keywords such as "counting permutations, Stirling numbers", however I still have no idea.

EDIT: I am quite satisfied with the accepted answer which, as one of the first answers, claims that $S_n = \lfloor n! e \rfloor$ and presents some numerical results. However, if you want to know how to prove it, please refer to the answer given by @Omran Kouba and give it an upvote.

Answer 1

The sum has a closed form for $n\ge 1$

$$e=\frac 1 {0!}+\frac 1 {1!}+\frac 1{2!}+\frac 1{3!}+...$$

What you want is : $$S=n!(\frac{1}{0!}+\frac{1}{1!}...\frac{1}{n!})$$

$$S= \lfloor n !e\rfloor$$

This works for many $n\ge1$ tested by me. If it decomposes at large $n$, error will be very less.

$S_1=2, \lfloor{1!e}\rfloor=2$

$S_2=5, \lfloor{2!e}\rfloor=5$

$S_3=16, \lfloor{3!e}\rfloor=16$

$S_{10}=9864101,\lfloor{10!e}\rfloor=9864101 $

$S_{20}=6613313319248080001=\lfloor{20!e}\rfloor $

Here is a plot of their difference by wolfram alpha :

Wolfram alpha is unable to draw graph correctly for their quotient, but here it is:

As you can see the $y$ axis has nothing but $1$. Maybe this is due to this very small scale.

Answer 2

You can get a quite good approximation like this:

$\begin{array}\\ S_n &=\sum_{k=0}^{n} \frac{n!}{(n-k)!}\\ &=n!\sum_{k=0}^{n} \frac{1}{k!}\\ &=n!(e-\sum_{k=n+1}^{\infty} \frac{1}{k!})\\ &=n!e-n!\sum_{k=n+1}^{\infty} \frac{1}{k!}\\ &=n!e-\frac1{n+1}\sum_{k=n+1}^{\infty} \frac{(n+1)!}{k!}\\ &=n!e-\frac1{n+1}(1+d_n)\\ \end{array} $

where $d_n$ is about $\frac1{n+1}$.

Therefore $S_n$ is very close to $n!e$.

Answer 3

$$S_n = \sum_{k=0}^{n} {n \choose k} k! = \sum_{k=0}^{n} \frac{n!}{(n-k)!}=e \Gamma (n+1,1)$$ where appears the incomplete gamma function.

Taking into account the previous answers, let me write $$S_n=e ~n!~\frac{\Gamma (n+1,1)}{n!}$$ For $n>5$, the last term is extremely close to $1$. If we compute $$R_n=\frac{\Gamma (n+1,1)}{n!}-1$$ we find $R_5=-0.000594185$,$R_{10}=-1.00478*10^{-8}$,$R_{15}=-1.86517*10^{-14}$,$R_{100}=-2.04281*10^{-14}$,$R_{1000}=5.90639*10^{-13}$ and so on !

So the approximation given by other participants $S_n \simeq e ~n!$ is clearly extremely good.

Answer 4

In fact all the previous posts propose something like $S_n=\lfloor n!e\rfloor$ but without an explicit proof. Here is one. Define $u_n=\sum_{k=0}^n\frac{1}{k!}$ and $v_n=u_n+\frac{1}{n!\cdot n}$ it is an easy task to prove that $(v_n)$ is decreasing. This implies that $u_{n+1}\leq e\leq v_n$ for every $n\geq 1$. This gives the following inequality $$\forall\,n\geq1\qquad S_n+\frac{1}{n+1}\leq n! e\leq S_n+\frac{1}{n}$$ or equivalently $$ n!e-1\leq n!e-\frac{1}{n}\leq S_n<n!e $$ But $S_n$ is an integer, so the previous inequality proves that $S_n=\lfloor n!e\rfloor$.