8
$\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, 2016 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$ Nov 18, 2016 at 14:19
  • $\begingroup$ I want to know why that is true. A derivation of the formula $\endgroup$ Nov 18, 2016 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, 2016 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$ Nov 18, 2016 at 15:52

2 Answers 2

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

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

$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – kgkmeekg
    Jun 13, 2021 at 18:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – K. Miller
    Jun 14, 2021 at 11:40
0
$\begingroup$

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}

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Community Bot
    Oct 3, 2022 at 20:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .