> If you take the averaged sum over all choices of signs $$\frac{1}{2^k}
> \sum_{\varepsilon_i = \pm 1} (\varepsilon_1x_1 + \cdots +
> \varepsilon_kx_k)^r$$ we see that only the terms with even exponents
> survive. If we place all $x_i=1$ we get the quantity that you are
> interested in. This is more explicitly equal to $$ \frac{1}{2^k}
> \left( \sum_{m=0}^k {k \choose m} (k-2m)^r \right).$$

 – Gjergji Zaimi, Aug 24 at 0:45

> The sum is the coefficient of $x^r/r!$ in $\cosh^kx$.

 – Ira Gessel, Aug 24 at 3:53

> See also [http://mathoverflow.net/questions/73613/...][1]

 – Max Alekseyev Aug 24 at 9:38 


  [1]: http://mathoverflow.net/questions/73613/what-is-this-restricted-sum-of-multinomial-coefficients