What is this restricted sum of multinomial coefficients? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T15:40:10Z http://mathoverflow.net/feeds/question/73613 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73613/what-is-this-restricted-sum-of-multinomial-coefficients What is this restricted sum of multinomial coefficients? Simon Rose 2011-08-24T22:06:22Z 2011-08-25T08:12:12Z <p>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?</p> <p>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.</p> <p>This arises in computing the coefficients of the power series of $\big(\sin(x)\big)^k$.</p> http://mathoverflow.net/questions/73613/what-is-this-restricted-sum-of-multinomial-coefficients/73616#73616 Answer by Max Alekseyev for What is this restricted sum of multinomial coefficients? Max Alekseyev 2011-08-24T22:38:05Z 2011-08-24T22:49:45Z <p>$\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$.</p> <p>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}.$$</p> <p>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> <p>P.S. This formula resembles one for Stirling number of the second kind (formula (10) at <a href="http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html" rel="nofollow">MathWorld</a>) but not quite.</p> http://mathoverflow.net/questions/73613/what-is-this-restricted-sum-of-multinomial-coefficients/73628#73628 Answer by Brendan McKay for What is this restricted sum of multinomial coefficients? Brendan McKay 2011-08-25T04:06:27Z 2011-08-25T04:18:05Z <p>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.</p> <p>ADDED: <a href="http://oeis.org/A136630" rel="nofollow">http://oeis.org/A136630</a> OEIS sequence A136630 is about these numbers.</p> http://mathoverflow.net/questions/73613/what-is-this-restricted-sum-of-multinomial-coefficients/73639#73639 Answer by Max Alekseyev for What is this restricted sum of multinomial coefficients? Max Alekseyev 2011-08-25T08:12:12Z 2011-08-25T08:12:12Z <p>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.</p>