What is this restricted sum of multinomial coefficients? - MathOverflow

What is this restricted sum of multinomial coefficients?

2011-08-24T22:06:22Z

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

Answer by Max Alekseyev for What is this restricted sum of multinomial coefficients?

2011-08-24T22:38:05Z

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

Answer by Brendan McKay for What is this restricted sum of multinomial coefficients?

2011-08-25T04:06:27Z

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.

Answer by Max Alekseyev for What is this restricted sum of multinomial coefficients?

2011-08-25T08:12:12Z

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.