Closed form expression for sum involving Stirling numbers

Question

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!

Answer 1

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.

Answer 2

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.$$