<s>[INST] Is there a closed form expression for $\sum_{1\le i_1 \le i_2 \le \dots \le i_k \le n} i_1 i_2 \dots i_k$? These sums showed up in a probability problem I was working on. They're not quite the Stirling numbers of the first kind since it's possible to have e.g. $i_1 = i_2$. Denoting the sum by $(k\mid n)$ we have the recurrence relation
$(k\mid n) = n(k-1\mid n) + (k\mid n-1)$
I thought maybe the average term of the sum would be similar to the average product over a random list of $k$ numbers from $1$ to $n$. But it seems to always be a few times greater.
I'm beginning to despair of there being a closed form expression for $(k\mid n)$ in terms of factorials and powers. Does anyone know how to analyze the sum further and perhaps find a good approximation?
 [/INST] We get from first principles the generating function where we mark
multisets containing some number of instances of $q$ giving the factor
being contributed and the exponent of $z$ how often  it occurs:
$$[z^k] \prod_{q=1}^n (1+qz+q^2z^2+q^3z^3+\cdots)
= [z^k] \prod_{q=1}^n \frac{1}{1-qz}
\\ = \frac{1}{n!} [z^k] \prod_{q=1}^n \frac{1}{1/q-z}
= (-1)^n \frac{1}{n!} [z^k] \prod_{q=1}^n \frac{1}{z-1/q}.$$
Now using partial fractions by residues we have
$$(-1)^n \frac{1}{n!} [z^k]
\sum_{p=1}^n \frac{1}{z-1/p}
\prod_{q=1}^{p-1} \frac{1}{1/p-1/q}
\prod_{q=p+1}^n \frac{1}{1/p-1/q}
\\ = (-1)^n \frac{1}{n!} [z^k]
\sum_{p=1}^n \frac{1}{z-1/p}
\prod_{q=1}^{p-1} \frac{pq}{q-p}
\prod_{q=p+1}^n \frac{pq}{q-p}
\\ = (-1)^n \frac{1}{n!} [z^k]
\sum_{p=1}^n \frac{p^{n-1}}{z-1/p}
\prod_{q=1}^{p-1} \frac{q}{q-p}
\prod_{q=p+1}^n \frac{q}{q-p}
\\ = (-1)^n [z^k]
\sum_{p=1}^n \frac{p^{n-2}}{z-1/p}
\prod_{q=1}^{p-1} \frac{1}{q-p}
\prod_{q=p+1}^n \frac{1}{q-p}
\\ = (-1)^n [z^k]
\sum_{p=1}^n \frac{p^{n-2}}{z-1/p}
\frac{(-1)^{p-1}}{(p-1)!} \frac{1}{(n-p)!}
\\ = (-1)^n \frac{1}{n!} [z^k]
\sum_{p=1}^n \frac{p^{n-1}}{z-1/p} {n\choose p} (-1)^{p-1}
\\ = (-1)^n \frac{1}{n!} [z^k]
\sum_{p=1}^n \frac{p^{n}}{pz-1} {n\choose p} (-1)^{p-1}
\\ = (-1)^n \frac{1}{n!} [z^k]
\sum_{p=1}^n \frac{p^{n}}{1-pz} {n\choose p} (-1)^p
\\ = (-1)^n \frac{1}{n!}
\sum_{p=1}^n  {n\choose p} (-1)^p p^{n+k}.$$
We may lower $p$ to zero and obtain
$$\frac{1}{n!}
\sum_{p=0}^n  {n\choose p} (-1)^{n-p} p^{n+k}
= {n+k \brace n}.$$
</s>