# Closed form expression for sum involving Stirling numbers

I am trying to find a closed form expression (or a more easily computable expression) for the sum

$$\sum_{k=1}^m \left({m\brace{k-1}} \cdot (n)_k\right)$$,

where $${m\brace{k-1}}$$ denotes a Stirling number of the second kind (number of ways of partitioning $$n$$ objects into $$k-1$$ nonempty sets) and $$(n)_k := n(n-1)\cdots (n-k+1)$$. Using the recurrence formula $${m+1\brace{k}} = k{m\brace{k}} + {m\brace{k-1}}$$, we could try to evaluate

$$\sum_{k=1}^m \left(k \cdot {m\brace{k}} \cdot (n)_k\right)$$

instead. I was wondering if anyone has any ideas on how to simplify these sums?

Thank you!

For an algebraic proof start from

$$\sum_{k=1}^m {m\brace k-1} n^{\underline{k}}.$$

We then have the alternate form

$$n \sum_{k=1}^m {m\brace k-1} (n-1)^{\underline{k-1}} \\ = n \times m! [z^m] \sum_{k=1}^m \frac{(\exp(z)-1)^{k-1}}{(k-1)!} (n-1)^{\underline{k-1}} \\ = n \times m! [z^m] \sum_{k=1}^m {n-1\choose k-1} (\exp(z)-1)^{k-1} \\ = n \times m! [z^m] \sum_{k=0}^{m-1} {n-1\choose k} (\exp(z)-1)^{k}.$$

Now $$(\exp(z)-1)^k = z^k + \cdots$$ so this is

$$- n \times m! \times {n-1\choose m} + n \times m! [z^m] \sum_{k=0}^{m} {n-1\choose k} (\exp(z)-1)^{k}.$$

Apply it a second time to obtain (coefficient extractor enforces the range):

$$- n^{\underline{m+1}} + n \times m! [z^m] \sum_{k\ge 0} {n-1\choose k} (\exp(z)-1)^{k} \\ = - n^{\underline{m+1}} + n \times m! [z^m] \exp((n-1)z) \\ = - n^{\underline{m+1}} + n \times (n-1)^m.$$

Split the Pochhammer symbol and reindex, discarding the unsupported term, to get $$\sum_{k=1}^m {m\brace{k-1}} (n)_k = n \sum_{k=1}^{m-1} {m \brace k} (n-1)_k$$ Then the term $${m \brace k} (n-1)_k$$ counts functions from a set of size $$m$$ to a set of size $$n-1$$ with range of size $$k$$: we partition the set of size $$m$$ into $$k$$ subsets and assign each one a distinct value to map to.

$$\sum_{k=1}^m {m \brace k} (n-1)_k$$ counts all functions from a set of size $$m$$ to a set of size $$n-1$$, so $$\sum_{k=1}^m {m \brace k} (n-1)_k = (n-1)^m$$.

Therefore $$n \sum_{k=1}^{m-1} {m \brace k} (n-1)_k = n \left((n-1)^m - {m \brace m} (n-1)_m \right) = n(n-1)^m - (n)_{m+1}$$

When $$n=m$$ the terms are OEIS A209290.