Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
what is the meaning/definition of $nPk$? –  Mercy 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 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 3

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

share|improve this answer

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

share|improve this answer
    
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)$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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