For a paper I was working on recently I needed to find the value of the following sum:


$$S(n,k) = \sum\_{i\_1 = 1}^n \sum\_{i\_2 = i\_1+1}^n \cdots \sum\_{i\_k=i\_{k-1}+1}^n \frac{1}{i\_1 i\_2 \cdots i\_k}.$$ 


I found a couple of references (by [Adamchik](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.2010&rep=rep1&type=pdf) and [Cheon and El-Mikkaway](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.6494&rep=rep1&type=pdf)) that have an expression for $S(n,k)$ as a polynomial containing generalized harmonic numbers $H\_n^{(r)}$, where
$$H\_n^{(r)} = \sum\_{j=1}^n \frac{1}{j^r}.$$
For example, 
$$S(n,2) = \frac{1}{2}\left(H\_n^2 - H^{(2)}\_n \right),$$
$$S(n,3) = \frac{1}{6}\left(H\_n^3 - 3H\_n H^{(2)}\_n + 2 H\_n^{(3)}\right),$$
$$S(n,4) = \frac{1}{24}\left(H\_n^4 - 6 H^2\_n H\_n^{(2)} + 3 (H\_n^{(2)})^2 + 8 H\_n H\_n^{(3)} - 6 H\_n^{(4)}\right).$$


Neither of these papers considers the corresponding polynomial sequence of indeterminates (the polynomials before substituting in the generalized harmonic numbers), though. Calculations for small values of $n$ indicate that these are the [cycle index polynomials of the symmetric groups](http://www-itp.particle.uni-karlsruhe.de/~wl/EISpub/A036039.text), with the sign pattern such that each factor of $H\_n^{(r)}$ contributes a $+1$ if $r$ is odd and a $-1$ if $r$ is even. 


Could someone give a proof of this, particularly one with a combinatorial flavor that gives some real insight into why the cycle index polynomials of the symmetric groups show up here (assuming that they do)? 


(For the record, I don't need this answered for my paper. I just want to know for my own sake.)


As a side note, the papers also give the extremely (and, to me, surprisingly) simple expression $$S(n,k) = \frac{1}{n!} \left[ n+1 \atop k+1 \right],$$ where $\left[ n \atop k \right]$ is an unsigned Stirling number of the first kind.



Can this nested sum be expressed in terms of generalized harmonic numbers and the cycle index polynomials of the symmetric groups?
One can rephrase Qiaochu's argument without using symmetric functions as follows:
A standard property of $\left[ n+1\atop k+1\right]$ is the generating function
 $$ \sum\_{k=0}^{n+1}\left[ n+1\atop k\right]t^k = t(t+1)(t+2)\cdots (t+n). $$
Equating coefficients of $t^{k+1}$ gives the result
 $$ S(n,k) =\frac{1}{n!}\left[ n+1\atop k+1\right]. $$
Now if the cycle index of the symmetric group $S\_k$ is $Z\_k(x\_1,x\_2,\dots,x\_k)$,
then it is well-known that
 $$ \sum\_k Z\_k(x\_1,x\_2,\dots)t^k = \exp\sum\_{r\geq 1}x\_r\frac{t^r}{r}. $$
Put $x\_r=(-1)^{r-1}H\_n^{(r)}$ to get
 $$ \sum\_{k\geq 0} Z\_k(H\_n^{(1)},-H\_n^{(2)},\dots)t^k = \left(1+t\right)\left(1+\frac t2\right)\cdots 
 \left(1+\frac tn\right), $$
from which it is immediate that $S(n,k)=Z\_k(H\_n,-H\_n^{(2)},\dots,(-1)^{k-1}H\_n^{(k)})$.


