Sum involving Stirling numbers of the second kind

Question

Is it possible to simplify this sum:

$\sum\limits_{k=1}^{n} {n\brace k} (x)_k k =?$

Where, $ {n\brace k}$ are Stirling numbers of the second kind and $(x)_k$ if a falling factorial.

Note: it is well known that:

$\sum\limits_{k=1}^{n} {n\brace k} (x)_k = x^n$

Answer 1

We can take advantage of the recurrence

$${{n+1}\brace k}=k{n\brace k}+{n\brace{k-1}}$$

to get

$$\begin{align*} \sum_{k=1}^nk{n\brace k}x^{\underline k}&=\sum_{k=1}^n\left({{n+1}\brace k}-{n\brace{k-1}}\right)x^{\underline k}\\\\ &=\sum_{k=1}^n{{n+1}\brace k}x^{\underline k}-\sum_{k=1}^n{n\brace{k-1}}x^{\underline k}\\\\ &=x^{n+1}-x^{\underline{n+1}}-x\sum_{k=0}^{n-1}{n\brace k}(x-1)^{\underline k}\\\\ &=x^{n+1}-x^{\underline{n+1}}-x\big((x-1)^n-(x-1)^{\underline n}\big)\\\\ &=x^{n+1}-x(x-1)^n\;. \end{align*}$$

Answer 2

By way of enrichment here is a proof using generating functions. Suppose we seek to evaluate $$\sum_{k=0}^n {n\brace k} k q^{\underline{k}} = \sum_{k=0}^n {n\brace k} k {q\choose k} k!$$ with $q$ a positive integer.

The combinatorial class of set partitions marked by the number of parts is $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}(\mathcal{U}\times \textsc{SET}_{\ge 1}(\mathcal{Z})).$$ This gives the generating function $$G(z, u) = \exp(u(\exp(z)-1))$$ which immediately yields $${n\brace k} = n! [z^n] \frac{1}{k!} \left(\exp(z)-1\right)^k.$$

This gives for the sum $$n! [z^n] \sum_{k=0}^n k {q\choose k} k! \frac{1}{k!} \left(\exp(z)-1\right)^k \\ = n! [z^n] \sum_{k=0}^n k {q\choose k} \left(\exp(z)-1\right)^k.$$

Observe that $$((1+x)^n)' = n(1+x)^{n-1} = \left(\sum_{p=0}^n {n\choose p} x^p\right)' = \sum_{p=1}^n p {n\choose p} x^{p-1}$$ so that $$nx (1+x)^{n-1} = \sum_{p=0}^n p {n\choose p} x^{p}.$$

There are two cases, first when $q\le n$ which gives $$n! [z^n] \sum_{k=0}^q k {q\choose k} \left(\exp(z)-1\right)^k$$ or $$n! [z^n] q (\exp(z)-1) \exp(z(q-1))$$

The second case is when $q\gt n.$ But $\exp(z)-1$ starts at $z$ so we can extend the summation from $n$ to $q$ because the additional terms do not contribute, again getting $$n! [z^n] q (\exp(z)-1) \exp(z(q-1))$$

This is $$n! [z^n] q (\exp(zq)-\exp(z(q-1))) = q \times q^n - q \times (q-1)^n = q^{n+1} - q (q-1)^n.$$