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 ?

$\endgroup$
  • $\begingroup$ what is the meaning/definition of $nPk$? $\endgroup$ – Mercy King Jun 21 '12 at 19:08
  • $\begingroup$ @Mercy: $n(n-1)(n-2)\cdots(n-k+1)$. The ordered combinations of $k$ elements from $n$ possibilities. $\endgroup$ – Arturo Magidin Jun 21 '12 at 19:08
  • $\begingroup$ 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!$ $\endgroup$ – Mercy King Jun 21 '12 at 19:16
  • $\begingroup$ @Mercy That is what I have written in my answer. $$\sum_{k=0}^{n} \dfrac1{k!} = \dfrac{e \Gamma(n+1,1)}{n!}$$ $\endgroup$ – user17762 Jun 21 '12 at 19:18
11
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

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

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

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