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, 2016 at 9:43
• I was told the number of strings that can be formed from a string of length 'n' is $n^n$. Nov 18, 2016 at 14:19
• I want to know why that is true. A derivation of the formula Nov 18, 2016 at 14:29
• What is "form" a string? Imagine the string is "abcd". How can you form different strings with it?
– RGS
Nov 18, 2016 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. Nov 18, 2016 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!}$$

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

• I am not really sure exactly how the Taytor's theorem is applied in the above derivation. Another reference I found here. Can I assume that since these are not closed form solutions both expression are correct ? Jun 13, 2021 at 18:15
• I have updated my answer to describe in more detail how Taylor's theorem is applied. In the reference you found, $S(n) = f(n) + 1$, so the expressions are equivalent. Jun 14, 2021 at 11:40

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}