6
$\begingroup$

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

Improve this question
$\endgroup$

3 Answers 3

Reset to default
13
$\begingroup$

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

Improve this answer
$\endgroup$
15
  • 4
    $\begingroup$ Combinatorial interpretation: number of of walks of length $l$ joining two antipodal points in the $k$-dimensional cube. $\endgroup$
    – Gjergji Zaimi
    Aug 25, 2011 at 9:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ira Gessel
    Aug 25, 2011 at 14:30
  • 1
    $\begingroup$ @Thoth: This is how we compute the odd part of a function with respect to $x_1$. $\endgroup$
    – Max Alekseyev
    Jan 30 at 22:37
  • 1
    $\begingroup$ @Thoth: No, you need to deal with one variable at a time. First, it's $\frac{1}{2}\big((x_1 + x_2 + \dots + x_k)^{\ell} - (-x_1 + x_2 + \dots + x_k)^{\ell}\big)$, then it's $$\frac{1}{4}\big((x_1 + x_2 + \dots + x_k)^{\ell} - (-x_1 + x_2 + \dots + x_k)^{\ell} - (x_1 - x_2 + \dots + x_k)^{\ell} + (-x_1 - x_2 + \dots + x_k)^{\ell}\big),$$ etc. Eventually you'll arrive at the formula with $2^k$ terms given in my answer. $\endgroup$
    – Max Alekseyev
    Jan 31 at 17:39
  • 1
    $\begingroup$ @Thoth: Gjergji's formula is the same as the first one for $s(\ell,k)$ in my answer. To arrive at the second formula, just group summands with the same value of the expression in parentheses. Namely, if there are $z$ minus-ones and $(k-z)$ plus-ones, then this value is $k-2z$. The number of such summands equals $\binom{k}{z}$, which is the number of ways to pick $z$ positions for minus-ones out of $k$ positions. $\endgroup$
    – Max Alekseyev
    Feb 1 at 15:21
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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). $\endgroup$
    – Noam D. Elkies
    Aug 25, 2011 at 4:09
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.