combinatorics - Can this binomial polynomial sum be simplified?

$$\sum_{k=0}^{n} \binom{n}{k} k^d$$

where $d$ is some fixed positive integer. Is this a well known sum that has a faster-than-$O(n)$ evaluation? It looks similar to Faulhaber's formula, except with binomial coefficients.

Answer

Suppose we seek to evaluate
$$S_d(n) = \sum_{k=0}^n {n\choose k} k^d.$$
using

$$k^d =
\frac{d!}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{d+1}} \exp(kz) \; dz.$$

This yields for the sum
$$\frac{d!}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{d+1}}
\sum_{k=0}^n {n\choose k} \exp(kz)

\; dz
\\ = \frac{d!}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{d+1}}
(1+\exp(z))^n
\; dz
\\ = \frac{d!}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{d+1}}
(2+\exp(z)-1)^n

\; dz
\\ = \frac{d!}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{d+1}}
\sum_{q=0}^n {n\choose q} 2^{n-q} (\exp(z)-1)^q
\; dz
\\ = \sum_{q=0}^n {n\choose q} 2^{n-q}
\times q! \times {d\brace q}$$

for a final answer of

$$\sum_{q=0}^d {n\choose q} 2^{n-q}
\times q! \times {d\brace q}.$$

This is a polynomial of degree $d$ in $n.$

The change of the upper limit is justified as follows: if $n\gt d$
then the Stirling number is zero for $n\ge q \gt d$ and we may replace
$n$ by $d$. On the other hand if $n\lt d$ the binomial coefficient is
zero for $n\lt q\le d$ and we may again replace $n$ by $d.$

Here we have used the species equation for labeled set partitions
$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$

which gives the bivariate generating function of the Stirling numbers
of the second kind $$\exp(u(\exp(z)-1)).$$