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

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 ?

• what is the meaning/definition of $nPk$? – Mercy King Jun 21 '12 at 19:08
• @Mercy: $n(n-1)(n-2)\cdots(n-k+1)$. The ordered combinations of $k$ elements from $n$ possibilities. – Arturo Magidin Jun 21 '12 at 19:08
• I don't think there is a closed form for that sum, but since $n(n-1)\cdots(n-k+1)=n!/(n-k)!$ you can at least write it as $n!\sum_{k=0}^n1/k!$ – Mercy King Jun 21 '12 at 19:16
• @Mercy That is what I have written in my answer. $$\sum_{k=0}^{n} \dfrac1{k!} = \dfrac{e \Gamma(n+1,1)}{n!}$$ – user17762 Jun 21 '12 at 19:18

## 3 Answers

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

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

• 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$. – Sasha Jun 21 '12 at 19:32

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