Value of an iterated sum

Question

I am interested in the number of function evaluations required to numerically evaluate an iterated integral of the form $$ \int_0^t \int_{t_1}^t \cdots \int_{t_{n-1}}^t f(t_1,\ldots,t_n) dt_n\cdots dt_1. $$ To this end, I consider approximating each integral with a simple left Riemann sum, where I subdivide the interval $[0,t]$ into $m$ partitions of equal size. It then seems sensible to me that the number of function evaluations required to evaluate the integral is $$ \sum_{k_1=1}^m \sum_{k_2 = k_1}^m \cdots \sum_{k_n = k_{n-1}}^m 1. $$ I would like to know something about the value of this sum. I have calculated the sum for the first few values of $n$. For example, it is immediate that for $n=1$, we have $$ \sum_{k_1=1}^m 1 = m, $$ while for $n=2$, we have $$ \sum_{k_1=1}^m \sum_{k_2=k_1}^m 1 = \sum_{k_1=1}^m (m-k_1+1) =\sum_{k_1=1}^m 1 = \frac{m(m+1)}{2}, $$ and for $n=3$, we obtain $$ \sum_{k_1=1}^m \sum_{k_2=k_1}^m \sum_{k_3=k_2}^m 1 = \sum_{k_1=1}^m\sum_{k_2=k_1}^m (m-k_2+1) =\sum_{k_1=1}^m \sum_{k_2=1}^{m-k_1+1} k_2\\ =\sum_{k_1=1}^m \frac{(m-k_1+1)(m-k_1+2)}{2} =\sum_{k_1=1}^m \frac{(k_1+1)k_1}{2}\\ =\frac{1}{2}\left(\frac{2m^3+3m^2+m}{6}+\frac{m(m+1)}{2}\right) =\frac{2m^3+6m^2+4m}{12}\\ =\frac{m^3+3m^2+2m}{6}. $$ My question is: How does this extend to $m>3$?

Answer 1

it's $\sum _{k=0}^n \frac{m^k (-1)^{k+n} S_n^{(k)}}{n!}$ (unsigned Stirling numbers of the first kind)
or, equivalently, the 'factorial power' $\frac{(-1)^n (-m)^{(n)}}{n!}$
see http://oeis.org/A132393 and http://oeis.org/A094638