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

$\endgroup$

3 Answers 3

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.

$\endgroup$
15
  • 4
    $\begingroup$ Combinatorial interpretation: number of of walks of length $l$ joining two antipodal points in the $k$-dimensional cube. $\endgroup$ 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$ 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$ 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$ 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.

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

$\endgroup$

Your Answer

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

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