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?

Here I will show by induction that the Stirling numbers of the second kind give the general answer for the multisubset sum: with $Q_{n,k}$ being the set of all $k$-multisubsets of $[n]=\{1,\dots,n\}$,
$$\sum_{s\in Q_{n,k}}\prod_{i=1}^ks_i=S(n+k,n)$$
For $n=1$ the equation holds since the only multisubset in $Q_{1,k}$ is $\{1,1,\dots,1\}$, leading to a sum of $1$, while $S(1+k,1)=1$.
For $k=1$ the equation holds because the multisubset sum reduces to a sum of the numbers in $[n]$:
$$\sum_{i=1}^ni=\binom{n+1}2=S(n+1,n)$$
Now for $n,k>1$ the multisubsets in $Q_{n,k}$ can be separated into those with the largest possible element $n$ and those without it. The first subset of multisubsets is $Q_{n,k-1}$ with $n$ added to each multisubset; the second subset is $Q_{n-1,k}$. Thus
$$\sum_{s\in Q_{n,k}}\prod_{i=1}^ks_i=n\sum_{s\in Q_{n,k-1}}\prod_{i=1}^ks_i+\sum_{s\in Q_{n-1,k}}\prod_{i=1}^ks_i$$
Assuming the relation is true for $(n,k-1)$ and $(n-1,k)$ – inducting on $n+k$:
$$\sum_{s\in Q_{n,k}}\prod_{i=1}^ks_i=nS(n+k-1,n)+S(n+k-1,n-1)$$
But $S(n,k)=kS(n-1,k)+S(n-1,k-1)$, so the left-hand side is $S(n+k,n)$ by substituting $(n,k)\leftarrow(n+k,n)$. This proves the induction, so the multinomial sum is $S(n+k,n)$ for all $n,k\ge1$.
