Multinomial theorem: Number of elements where all coefficients have even powers.. Consider $(a_1+a_2+ \cdots + a_n)^r$. We know that it has $n^r$ elements. I want to calculate the number of elements, where all $a_i$ coefficiants have even powers, i.e. $(a_1+a_2+ \cdots + a_n)^r = \sum_{k_1+k_2+ \cdots + k_n = r} \frac{r!}{k_1! k_2! \cdots k_n!}a_1^{k_1} \cdots a_n^{k_n},$ to calculate the following sum $\sum_{k_1+k_2+ \cdots + k_n = r, \forall k_i even} \frac{r!}{k_1! k_2! \cdots k_n!}.$ How can I calculate this sum? 
 A: Consider i.i.d. random variables $X_1, \ldots, X_n$ with $\operatorname{Pr}(X_i = -1) = \operatorname{Pr}(X_i = 1) = 1/2$ for all $i$. It is easy to see that $$\operatorname{E}[(X_1+\ldots+X_n)^r] = \operatorname{E}\left[\sum_{k_1+\ldots+k_n=r}{\frac{r!}{k_1!\ldots k_n!}X_1^{k_1}\ldots X_n^{k_n}}\right] = \sum_{k_1+\ldots+k_n=r,\  k_i {\text{ is even }} \forall i}{\frac{r!}{k_1!\ldots k_n!}}.$$
On the other hand, for all $0\leq k\leq n$, we have $$\operatorname{Pr}(X_1 + \ldots + X_n = -n+2k) = \frac{1}{2^n}{n\choose k}.$$ Therefore $$\operatorname{E}[(X_1+\ldots+X_n)^r] = \frac{1}{2^n}\sum_{k=0}^n {n\choose k}(-n+2k)^r.$$ Assume we are interested in the case when $r$ is relative small comparing to $n$, we can further deduce that the above is equal to $$\frac{1}{2^n}\sum_{k=0}^n {n\choose k}\sum_{i=0}^r{r\choose i}(-n)^{r-i}(2k)^i.$$
Now we have $$\sum_{k_1+\ldots+k_n=r,\  k_i {\text{ is even }} \forall i}{\frac{r!}{k_1!\ldots k_n!}} = \sum_{i=0}^r {r\choose i}(-n)^{r-i}\sum_{k=0}^n \frac{1}{2^n}{n\choose k}(2k)^i.$$
Note that for $i$ fixed, we have $$\sum_{k=0}^n\frac{1}{2^n}{n\choose k}k^i = \sum_{k=0}^n\frac{1}{2^n}{n\choose k}\sum_{j=0}^i S(i,j)(k)_j = \sum_{j=0}^iS(i,j)\sum_{k=0}^n\frac{1}{2^n}{n\choose k}(k)_j = \sum_{j=0}^iS(i,j)2^{-j}(n)_j,$$ where $S(i,j)$ is the Stirling number of the second kind and $(k)_j = k(k-1)\ldots(k-j+1)$. Plug in the above, we obtain $$\sum_{k_1+\ldots+k_n=r,\  k_i {\text{ is even }} \forall i}{\frac{r!}{k_1!\ldots k_n!}} = \sum_{i=0}^r {r\choose i}(-n)^{r-i}\sum_{j=0}^iS(i,j)2^{i-j}(n)_j.$$
