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.
 A: 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)).$$
A: For $d=1,2,3$, the results are $2^{n-1}n$, $2^{n-2}n(n+1)$ and $2^{n-3}n^2(n+3)$
respectively. For higher values $d$, experiment with Wolfram  to find a pattern.
Note, that for $d>3$ you need the generalized hypergeometric function.
