8
$\begingroup$

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 Kouta and give it an upvote.

$\endgroup$
  • 2
    $\begingroup$ Assuming I've understood your question, it doesn't look like it. See oeis.org/A000522 $\endgroup$ – Alex Wertheim May 24 '14 at 3:50
  • 1
    $\begingroup$ Apparently for $n\ge 1$ it is $\lfloor{n!e}\rfloor$. $\endgroup$ – evil999man May 24 '14 at 4:10
12
$\begingroup$

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 : enter image description here

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

enter image description here

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

$\endgroup$
  • 1
    $\begingroup$ Nice y-axis, Wolfram alpha! $\endgroup$ – qwr May 24 '14 at 4:31
  • 1
    $\begingroup$ Wolfram alpha acknowledges compliment. $\endgroup$ – evil999man May 24 '14 at 4:39
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1; It is perfect to prove that $S_n = \lfloor n! e \rfloor$. However, I decided (not an easy choice) to accept the answer posted earlier. Thanks. $\endgroup$ – hengxin May 24 '14 at 6:26
  • 1
    $\begingroup$ @hengxin: you are free to accept whatever answer you think is best, but it is customary to accept the best answer, not necessarily the first answer. The FAQ says: "Choose one answer that you believe is the best solution to your problem." and "Accepting an answer is not mandatory; do not feel compelled to accept the first answer you receive. Wait until you receive an answer that answers your question well." $\endgroup$ – robjohn May 27 '14 at 7:08
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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