Mathematically calculate the time complexity of all permutations of a string

Question

I am trying to mathematically analyze the complexity of the following code

void perm(String str){
  perm(str, "");
}

void perm(String str, String prefix){
   if(str.length() == 0){
       System.out.println(prefix);
   } else{
      for(int i = 0; i < str.length(); i++){
          String rem = str.substring(0, i) + 
                       str.substring(i + 1);
          perm(rem, prefix + str.charAt(i));
      }
   }
}

I saw this website that explains the complexity using common sense but I want to try and solve this mathematically.

the equations I got are

(1) $T(n) = n(n+T(n-1)) = n^2 + nT(n-1)$

(2) $T(n) = n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + ... = \frac{nn!}{(n-1)!} + \frac{(n-1)n!}{(n-2)!} + \frac{(n-2)n!}{(n-3)!} + ... $

(3) $T(n) = n!(\frac{n}{(n-1)!} + \frac{n-1}{(n-2)!} + \frac{n-2}{(n-3)!} + ... + \frac{1}{0!})$

now I am stuck as I can't seem to find the value of the sum..

was the calculations right? got any tips for finding the value of $(\frac{n}{(n-1)!} + \frac{n-1}{(n-2)!} + \frac{n-2}{(n-3)!} + ... + \frac{1}{0!})$ ?

Thanks

Answer 1

\begin{eqnarray*} \sum_{k=1}^n\frac k{(k-1)!}x^k &\simeq& \sum_{k=1}^\infty\frac k{(k-1)!}x^k \\ &=&\left(x\frac{\mathrm d}{\mathrm dx}\right)^2 \sum_{k=1}^\infty\frac{x^k}{k!} \\ &=& \left(x\frac{\mathrm d}{\mathrm dx}\right)^2\left(\mathrm e^x-1\right) \\ &=&\left(x^2+x\right)\mathrm e^x\;. \end{eqnarray*}

Evaluating at $x=1$ yields $2\mathrm e$ as an estimate of your sum for large $n$.