I'm finding a probability related to graphs (It's $\frac{Q(n)}{n}$).
$$Q(n) = 1 + \frac{n-1}{n} + \frac{(n-1)(n-2)}{n^2} + \ldots + \frac{(n-1)(n-2)\cdots 1}{n^{n-1}} = \sum_{k=1}^n \frac{n!}{(n-k)! n^k}$$ It can be calculated assymptotically by means of Stirling approximation. However, I thought I can calculate it more precisely using Stirling numbers of the first kind: $$Q(n) = \frac{{n^{n-1}\times n+n^{n-2}\times n(n-1)+\ldots+n^0\times n(n-1)\cdots 1}}{n^n}$$ $$= \frac{1}{n^n}\Big[\big(s(1,1)+s(2,2)+\ldots+s(n,n)\big)n^n+\big(s(2,1)+\ldots+s(n,n-1)\big)n^{n-1}+\ldots+\big(s(n-1,1)+s(n,2)\big)n^2+s(n,1)n\Big]$$ Where $s(n,k)$ is signed Stirling number of the first kind. First, are the calculations OK? If yes, how can we simplify this stranger summation? I think if there is an identity for $$\sum_{i=1}^n{i+c\brack i}$$ as a polynomial of $n$, the expression will be simpler ultimately. (${i+c\brack i}$ is the unsigned Stirling number of the first kind and $c$ is a constant.)