8

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.

Tobi Alafin
  • 1,187
  • 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 09: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
  • I think this is the answer of how many n digit strings you can form by using n chars (should be distinct). Each position has n choices, so n^n. For example using "ab", you have aa, ab, ba, bb. – karakfa Nov 18 '16 at 15:52
  • Oh. Yh, I realised it doesn't give the number of how many different strings can be formed from an n character string without repetition of any character in each string. That's what I was asking. – Tobi Alafin Nov 18 '16 at 15:58

2 Answers2

9

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

K. Miller
  • 4,688
  • 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 ? – kgkmeekg Jun 13 '21 at 18:15
  • 1
    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. – K. Miller Jun 14 '21 at 11:40
0

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}

Osman GOKTURK
  • 1
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Community Oct 03 '22 at 20:30