11
$\begingroup$

what is the sum of following permutation series $nP0 + nP1 + nP2+\cdots+ nPn$ ?

I know that $nC0 + nC1 +\cdots + nCn = 2^n$, but not for permutation. Is there some standard result for this ?

  • 0
    @Mercy That is what I have written in my answer. $\sum_{k=0}^{n} \dfrac1{k!} = \dfrac{e \Gamma(n+1,1)}{n!}$2012-06-21

3 Answers 3

11

You can write this as

$ S(n) = n! \left( {1 \over 0!} + {1 \over 1!} + \cdots + {1 \over n!} \right) $

and now recall that $e = 1/0! + 1/1! + 1/2! + \cdots $. So in fact

$ S(n) = n! \left( e - \left( {1 \over (n+1)!} + {1 \over (n+2)!} + \cdots \right) \right) $

and we can rearrange this to give

$ S(n) = n! \times e - \left( {1 \over (n+1)} + {1 \over (n+1)(n+2)} + \cdots \right). $

Call the expression in parentheses $g(n)$ -- that is,

$ g(n) = {1 \over (n+1)} + {1 \over (n+1)(n+2)} + {1 \over (n+1)(n+2)(n+3)} + \cdots $.

Then clearly

$ g(n) < {1 \over n} + {1 \over n^2} + {1 \over n^3} + \cdots $

and by the usual formula for the sum of a geometric series,

$ g(n) < {1/n \over 1-(1/n)} = {1 \over n-1}. $

In particular if $n > 2$ we have $g(n) < 1$ and therefore $(n! \times e) - 1 < S(n) < n! \times e$. But $S(n)$ is a sum of integers and is therefore an integer. So $S(n) = \lfloor n! \times e \rfloor$ -- that is, $S(n)$ is the greatest integer less than $n! \times e$. For example $4! \times e \approx 65.23$ and $S(4) = 65$.

This sequence is A000522 in the OEIS and the formula I gave here is given there without proof.

Also, the number of derangements of n elements is given by $n! (1/0! - 1/1! + 1/2! - \cdots \pm 1/n!)$ and can similarly be proven to be the integer closest to $n!/e$.

4

Let us call the sum $S(n)$. We have $S(1) = 1P0 + 1P1 = 1+1 = 2$.

For $n\gt 1$, we can factor out $n$ to get $\begin{align*} S(n) &= nP0 + nP1 + nP2 + \cdots + nPn\\ &= 1+ n + n(n-1) + \cdots + n!\\ &= 1+ n\Bigl( 1+(n-1) + (n-1)(n-2) + \cdots + (n-1)!\Bigr)\\ &= 1+nS(n-1). \end{align*}$

Thus, the sequence begins: $\begin{align*} S(1) &= 2\\ S(2) &= 1 + 2S(1) = 5\\ S(3) &= 1+ 3S(2) = 16\\ S(4) &= 1+4S(3) = 65\\ S(5) &= 1+5S(4) = 326\\ &\vdots \end{align*}$

This is sequence A00522 on the On-Line Encyclopedia of Integer Sequences. The entry contains numerous connections; e.g., $S(n)$ is the permanent of the $n\times n$ matrix with $2$s in the diagonal and $1$s elsewhere; it also gives the formula from Marvis's post: $S(n) = \exp(1)\Gamma(n+1,1)\text{ where }\Gamma(z,t)=\int_{x\geq t} \exp(-x)x^{z-1}\, dx$

  • 0
    Also the exponential generating function for $S(n)$ has a nice form: $\sum_{n=0}^\infty \frac{t^n}{n!} S(n) = \sum_{n=0}^\infty \frac{t^n}{n!} \int_{1}^\infty x^n \mathrm{e}^{1-x} \mathrm{d} x = \int_1^\infty \mathrm{e}^{t x + 1 -x} \mathrm{d} x = \frac{\mathrm{e}^t}{1-t}$, valid for t < 1.2012-06-21
1

There is no "nice" closed form as such though it is related to the incomplete $\Gamma$ function.

$P(n,k) = \dfrac{n!}{(n-k)!}$. Hence, $\sum_{k=0}^{n} P(n,k) = n! \left( \sum_{k=0}^{n} \dfrac1{(n-k)!} \right) = n! \left( \sum_{k=0}^{n} \dfrac1{k!} \right)$ The above sum is related to the incomplete $\Gamma$ function, which is defined as $\Gamma(n+1,x) = \int_x^{\infty} t^{n} e^{-t} dt = n! e^{-x} \sum_{k=0}^n \left(\dfrac{x^k}{k!} \right)$ taking $n$ to be a positive integer. Setting $x=1$, we get that $\Gamma(n+1,1) = \dfrac{n!}e \left(\sum_{k=0}^n \dfrac1{k!} \right)$ Hence, $\sum_{k=0}^{n} P(n,k) = e \times \Gamma(n+1,1)$