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
    Commented 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
    Commented 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
    Commented Jan 30, 2023 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
    Commented Jan 31, 2023 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
    Commented Feb 1, 2023 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .