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