Magic relation for harmonic numbers I was doing same computations for an exercise and I came up with the following relation
$$\sum_{k=1}^n\frac{1}{k}=\sum_{j=1}^n\frac{1}{(j-1)!}\sum_{i_1+\dots+i_j=n\\i_1,\dots i_j\geq1}\frac{1}{i_1i_2\dots i_j}$$
for all $n\geq1.$
Any idea how to prove it algebraically?
Small result: I'm sure that the two sums are not equal terms by terms.
 A: We have using formal power series that the RHS is
$$\sum_{j=1}^n \frac{1}{(j-1)!}
[z^n] \left(\log\frac{1}{1-z}\right)^j
= [z^n] \sum_{j=1}^n \frac{1}{(j-1)!}
\left(\log\frac{1}{1-z}\right)^j.$$
Now since $\log\frac{1}{1-z} = z + \cdots$ we may extend $j$ beyond $n$
without contributing to the coefficient extractor:
$$[z^n] \sum_{j\ge 1} \frac{1}{(j-1)!}
\left(\log\frac{1}{1-z}\right)^j
\\ = [z^n] \log\frac{1}{1-z} \sum_{j\ge 1} \frac{1}{(j-1)!}
\left(\log\frac{1}{1-z}\right)^{j-1}
\\ = [z^n] \log\frac{1}{1-z}
\exp \log\frac{1}{1-z}
= [z^n] \frac{1}{1-z} \log\frac{1}{1-z}
= \sum_{k=1}^n \frac{1}{k} = H_n.$$
Remark. Restricting the proof to combinatorial methods we have for
the   combinatorial   class    $\mathcal{P}$   of   permutations   the
specification as sets of labeled cycles, which is
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{P} =    
\textsc{SET}(\textsc{CYC}(\mathcal{Z}))$$
Since permutations have EGF $\sum_{n\ge  0} n! z^n/n! = \frac{1}{1-z}$
we have the identity
$$\frac{1}{1-z} = \exp \log\frac{1}{1-z}$$
that was used above.
