Counting the sum of cycles of the elements in $S_n$. Let $\sigma\in S_n$ be given. Let us write $\sigma$ in its disjoint cycle decomposition. Define by $w(\sigma)$ the number of cycles (for instance if we have the permutation $1\mapsto 2, 2\mapsto 4, 3\mapsto 3, 4\mapsto 1, 5\mapsto 5$ we write it as $(124)(3)(5)$ so $w(\sigma)=3$).
I was asked to find $$A_n=\sum_{\sigma\in S_n}w(\sigma)$$I found the recursive formula $$A_n=n!+(n-1)!\left[\frac{A_{n-1}}{(n-1)!}+\frac{A_{n-2}}{(n-2)!}+\ldots+\frac{A_{1}}{1!}\right]$$
I was trying to tinker around with it to see if I could get a formula that does not rely on recursion, but failed at it. Any help or hint that would lead me towards making my solution for $A_n$ "better". 
 A: Let $b_n=\dfrac{A_n}{n!}$; then your recurrence can be rewritten
$$b_n=1+\frac1n\sum_{k=1}^{n-1}b_k\;,\tag{1}$$
with $b_1=1$. Calculate a few values: 
$$\begin{align*}
&b_1=1\\
&b_2=1+\frac12\cdot1=\frac32\\
&b_3=1+\frac13\left(1+\frac32\right)=\frac{11}6\\
&b_4=1+\frac14\left(1+\frac32+\frac{11}6\right)=\frac{25}{12}
\end{align*}$$
I recognize those as the first four harmonic numbers: $$b_n=H_n=\sum_{k=1}^n\frac1k\;.$$
And sure enough, the harmonic numbers do satisfy $(1)$:
$$\begin{align*}
1+\frac1n\sum_{k=1}^{n-1}H_k&=1+\frac1n\sum_{k=1}^{n-1}\sum_{i=1}^k\frac1i\\
&=1+\frac1n\sum_{i=1}^{n-1}\sum_{k=i}^{n-1}\frac1i\\
&=1+\frac1n\sum_{i=1}^{n-1}\frac{n-i}i\\
&=1+\frac1n\sum_{i=1}^{n-1}\left(\frac{n}i-1\right)\\
&=1+\sum_{i=1}^{n-1}\frac1i-\frac{n-1}n\\
&=1+H_{n-1}-1+\frac1n\\
&=H_n\;.
\end{align*}$$
Thus, $A_n=n!H_n$.
Added: Here’s another approach to the problem. It’s not too hard to prove that the number of $\pi\in S_n$ with $k$ cycles is $\left[n\atop k\right]$, a Stirling number of the first kind. These have the generating function $$\sum_{k\ge 0}\left[n\atop k\right]x^k=x^{\overline{n}}=x(x+1)(x+2)\dots(x+n-1)\;.$$ Differentiating yields
$$\begin{align*}
\sum_{k\ge 1}k\left[n\atop k\right]x^{k-1}&=\frac{d}{dx}\Big(x(x+1)(x+2)\dots(x+n-1)\Big)\\
&=\sum_{k=0}^{n-1}\frac{\prod_{i=0}^{n-1}(x+i)}{x+k}\;,
\end{align*}$$
and evaluating at $x=1$ yields $$\sum_{k\ge 1}k\left[n\atop k\right]=\sum_{k=0}^{n-1}\frac{n!}{k+1}=n!H_n\;.$$
A: This question is best addressed using the symbolic method.
Permutations are sets of cycles, having combinatorial class specification
$\mathfrak P(\mathfrak C(\mathfrak Z))$. Hence the corresponding exponential generating function (EGF) is $$ \exp \log \frac{1}{1-z} = \frac{1}{1-z},$$ where $$ \log \frac{1}{1-z} $$ is the EGF of labelled cycles. (These two are easily verified as there are $n!$ permutations and $n!/n$ cycles.)
If we want to count the number of cycles we need to mark each cycle with a new variable, $u$, which gives the mixed generating function
$$G(z, u) = \exp \left( u \log \frac{1}{1-z} \right).$$
Now a term $u^k z^n / n!$ in $G(z, u)$ represents a permutation of $n$ elements having $k$ cycles. To count these, we need to differentiate with respect to $u$ and set $u=1$, obtaining
$$ \left. \frac{d}{du} G(z, u) \right|_{u=1} =
\left. \exp \left( u \log \frac{1}{1-z} \right) \log \frac{1}{1-z} \right|_{u=1} =
\frac{1}{1-z} \log \frac{1}{1-z} .$$
But $$ [z^n] \frac{1}{1-z} \log \frac{1}{1-z} = H_n $$ by a trivial calculation and we are done.
There is much more on this method at Wikipedia. 
A: You can get an easier recurrence by considering the last element $n$ in the permutation.
Either $n$ occurs in a cycle of length at least $2$, or it forms a "cycle" on its own. In the former case taking it out of its cycle leaves a permutation of $n-1$ with the same number of cycles, and given a permutation of $n-1$ we can insert $n$ in $n-1$ places into an existing cycle, for a total contribution of $(n-1)A_{n-1}$ to $A_n$. In the latter case removing $n$ just leaves a permutation of $n-1$, which here arises in only one way; however the number of cycles is one more for the permutation of $n$ than it was for the permutation of $n-1$, so in all this contributes $A_{n-1}+(n-1)!$ to $A_n$ (the second term is for the extra cycle in $(n-1)!$ permutations). Since we have now accounted for every contribution once, we get
$$
  A_n=(n-1)A_{n-1}+A_{n-1}+(n-1)! = nA_{n-1} + (n-1)!
$$
One can simplify this by dividing by $n!$, giving
$$
  \frac{A_n}{n!}= \frac{A_{n-1}}{(n-1)!} + \frac1n,
$$
which together with $A_0=0$ obviously gives $\frac{A_n}{n!}=\sum_{i=1}^n\frac1i=H_n$ and $A_n=n!H_n$.
