Sum of Permutations from 0 to n

Question

In a question I asked on algorithms with time complexity of $f(x) = n^n$ I was told that enumerating the number of strings that can be formed from a string of length $n$ qualifies.

I.e the sum of all permutations of $n$ from $n$ to $0$ is $n^n$

$\sum ^n_{i=0} nPi$ $= n^n$

Can I please see an easy to understand derivation of that formula.

EDIT The above identity is wrong. I just tested it. Can I get a derivation of the formula for the sum of permutations.

Answer 1

Suppose you have $n$ distinct elements. Then the number of strings that can be formed of length $1$ to $n$ with distinct elements is

$$ f(n) = \sum_{k=1}^n \left( \begin{array}{c} n\\ k \end{array}\right) k! = \sum_{k=1}^n\frac{n!}{(n - k)!} = n!\sum_{k=0}^{n-1}\frac{1}{k!} $$

By Taylor's theorem we have that

$$ e = \sum_{k=0}^n\frac{1}{k!} + \frac{e^\xi}{(n+1)!} $$

for some $\xi\in(0,1)$. Multiplying through by $n!$ we arrive at

$$ n!e = n!\sum_{k=0}^n\frac{1}{k!} + \frac{e^\xi}{n+1} = f(n) + 1 + \frac{e^\xi}{n+1} $$

Since $e^\xi$ is an increasing function of $\xi$ we obtain

$$ \frac{1}{n+1} \leq en! - 1 - f(n) \leq \frac{e}{n+1} $$

for all integers $n \geq 1$. Since $f(n)$ is an integer it follows that

$$ f(n) = \lfloor en! - 1\rfloor $$

for all integers $n \geq 1$.

Answer 2

This is something different.

with the example of 3 letters: a,b,c allowing "aab" it is rather 3^{0}+3^{1}\ +3^{2}+3^{3}