# What is this restricted sum of multinomial coefficients?

It is relatively easy to show that $$\sum_{a_1 + \cdots + a_k=\ell} \binom{\ell}{a_1,\ldots,a_k} = k^\ell$$ where $\binom{\ell}{a_1, \ldots, a_k} = \frac{\ell!}{a_1!\cdots a_k!}$. What can be said if we want to compute the restricted sum $$s(\ell,k) = \sum_{a_1 + \cdots + a_k=\ell} \binom{\ell}{a_1,\ldots,a_k}$$ where we now restrict the summation to those $a_k$ which are odd? At the least, of course, we need that $\ell \geq k$ and that $\ell \equiv k \pmod 2$. Is this sum known in the literature?

The simplest case of $s(2k,2) = 2^{2k-1}$ can be easily verified, but I believe that this is an anomoly based on the fact that these are (secretly) binomial coefficients.

This arises in computing the coefficients of the power series of $\big(\sin(x)\big)^k$.

-

## 3 Answers

$\binom{\ell}{a_1,\dots,a_k}$ is the coefficient of $x_1^{a_1}\cdots x_k^{a_k}$ in the expansion of $$(x_1 + x_2 + \dots + x_k)^{\ell}.$$ The sum of all these coefficients is obtained by substituting $x_1=\dots=x_k=1$.

To eliminate even $a_1$, we can consider the expansion of $$\frac{1}{2}(x_1 + x_2 + \dots + x_k)^{\ell} - \frac{1}{2}(-x_1 + x_2 + \dots + x_k)^{\ell}.$$

Continuing this way, we eventually get $$s(\ell,k) = \frac{1}{2^k} \sum_{t_1,\dots,t_k=0}^1 (-1)^{t_1+\dots+t_k} ((-1)^{t_1}+\cdots+(-1)^{t_k})^{\ell}$$ $$=\frac{1}{2^k} \sum_{z=0}^k \binom{k}{z} (-1)^z (k-2z)^{\ell}.$$

P.S. This formula resembles one for Stirling number of the second kind (formula (10) at MathWorld) but not quite.

-
Combinatorial interpretation: number of of walks of length $l$ joining two antipodal points in the $k$-dimensional cube. – Gjergji Zaimi Aug 25 '11 at 9:09
This is the formula that you get by expanding $$\sinh^k z = \left( e^z - e^{-z}\over 2\right)^k$$ by the binomial theorem. These numbers are essentially central factorial numbers. – Ira Gessel Aug 25 '11 at 14:30

Seems like (but needs checking that) $$\sum \frac{1}{\ell!} s(\ell,k) z^\ell t^k = \exp(t \sinh(z)).$$ That could probably be used to find other formulas, recurrences, etc.

ADDED: http://oeis.org/A136630 OEIS sequence A136630 is about these numbers.

-
This probably comes back full circle to the original proposer's motivating problem of computing the coefficients of $\sin^k(x)$ (which are the same as the $\sinh^k(x)$ coefficients up to sign). – Noam D. Elkies Aug 25 '11 at 4:09

Another way to approach the original problem is to recall the formula: $$\cos(y)^k = \frac{1}{2^k} \sum_{j=0}^k \binom{k}{j}\cos((k-2j)y).$$ Plugging in $y=\frac{\pi}{2} - x$ would give an expansion for $\sin(x)^k$. I suspect eventually it would lead to the same formula that I gave in the previous answer.

-