# Sum of Permutations from 0 to n

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.

• What are you really asking? Do you want to know why it takes $n^n$ to compute all strings with length $n$, if you can use $n$ different characters? – RGS Nov 18 '16 at 9:43
• I was told the number of strings that can be formed from a string of length 'n' is $n^n$. – Tobi Alafin Nov 18 '16 at 14:19
• I want to know why that is true. A derivation of the formula – Tobi Alafin Nov 18 '16 at 14:29
• What is "form" a string? Imagine the string is "abcd". How can you form different strings with it? – RGS Nov 18 '16 at 14:34
• From string "abc": "a", "b", "c", "ab", "ac", "ba", "bc", "ca", "cb", "abc", "acb", "bac", "bca", "cab", "cba". That's what I mean. – Tobi Alafin Nov 18 '16 at 15:52

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

Using Taylor's theorem we can show that

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