7
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ – RGS Nov 18 '16 at 9:43
  • $\begingroup$ I was told the number of strings that can be formed from a string of length 'n' is $n^n$. $\endgroup$ – Tobi Alafin Nov 18 '16 at 14:19
  • $\begingroup$ I want to know why that is true. A derivation of the formula $\endgroup$ – Tobi Alafin Nov 18 '16 at 14:29
  • $\begingroup$ What is "form" a string? Imagine the string is "abcd". How can you form different strings with it? $\endgroup$ – RGS Nov 18 '16 at 14:34
  • $\begingroup$ From string "abc": "a", "b", "c", "ab", "ac", "ba", "bc", "ca", "cb", "abc", "acb", "bac", "bca", "cab", "cba". That's what I mean. $\endgroup$ – Tobi Alafin Nov 18 '16 at 15:52
6
$\begingroup$

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

$\endgroup$

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