Timeline for What is this restricted sum of multinomial coefficients?
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 9, 2023 at 22:07 | comment | added | Thoth | @MaxAlekseyev Thanks again for the comment. I think now that I understand completely all the part. Thanks for your time and patience. | |
| Feb 7, 2023 at 15:46 | comment | added | Max Alekseyev | @Thoth: I said that $k-2z$ is the value for the expression in parentheses. The corresponding summand value is $(-1)^z(k-2z)^\ell$, and there are $\binom{k}{z}$ such summands for each value of $z$. | |
| Feb 6, 2023 at 18:17 | comment | added | Thoth | hanks for the comment. I think now I understand the first part in $S(l,k)$. Now I am trying to understand is the second part. In one of you comments above you mention that there are $\binom{k}{z}$ summands that equals to $k-2z$. What I do not understand is how this information is used to construct $\sum_{z=0}^k \binom{k}{z} (-1)^z (k-2z)^{\ell}$. Can you please provide some details on the intuition to construct it? Any help is highly appreciated. | |
| Feb 1, 2023 at 21:36 | comment | added | Max Alekseyev | @Thoth: We have $\epsilon_i = (-1)^{t_i}$ for all $i$, and in the current settings $x_1=x_2=\dots=x_k=1$. | |
| Feb 1, 2023 at 15:56 | comment | added | Thoth | Second, the relation of $$\frac{1}{2^k}\sum_{\varepsilon_i=\pm 1}(\varepsilon_1x_1+\cdots+\varepsilon_k x_k)^r$$ with $$\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}$$ is not obvious to me right now from what I am aware. | |
| Feb 1, 2023 at 15:47 | comment | added | Thoth | First, I am trying to see the relation of $$\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),$$ with $$\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}.$$ In the second one there are exponents inside the $l$-th power that makes it hard to understand. In addition, the maximum value of $t_1,\dots,t_k$ in $\sum_{t_1,\dots,t_k=0}^1$ is $l$ instead of $1$? I have not have the necessary experience as it seems. | |
| Feb 1, 2023 at 15:21 | comment | added | Max Alekseyev | @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. | |
| Jan 31, 2023 at 22:05 | comment | added | Thoth | Thanks for the comment. However, I can not reproduce the result. I see the comment of @Gjergji Zaimi here but not intermediate steps are give when starting from $\frac{1}{2^k}\sum_{\varepsilon_i=\pm 1}(\varepsilon_1x_1+\cdots+\varepsilon_k x_k)^r$. Could you please provide these intermediate steps in your answer to fully understand the procedure? | |
| Jan 31, 2023 at 17:39 | comment | added | Max Alekseyev | @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. | |
| Jan 31, 2023 at 8:10 | comment | added | Thoth | Actually applying multinomial expansion I am getting $f_o(x_1, \dots,x_k) = \frac{1}{2} \left( \sum_{a_1 + \cdots + a_k=\ell} \binom{\ell}{a_1,\ldots,a_k} (1 - \prod_{i=1}^{k} (-1)^{a_i} \right)$. In addition, the superscripts $t_i$ in your answer are different from $a_i$? | |
| Jan 31, 2023 at 7:59 | comment | added | Thoth | Thanks I didn;t know that. So the odd part of $f(x_1, \dots, x_k) = (x_1 + \dots, x_k)^l$ is $f_o(x_1, \dots, x_k) = \frac{1}{2} (f(x_1, \dots, x_k) - f(-x_1, \dots, -x_k))$ ? I am trying to use this with the multinomial expansion $f(x_1, \dots, x_k) = \sum_{a_1 + \cdots + a_k=\ell} \binom{\ell}{a_1,\ldots,a_k} \prod_{i=1}^{k} x_i^{a_i}$ to get the first line of $s(l, k)$ but I could not reproduce your result. Could you please provide some intermediate step? Any help is highly appreciated! | |
| Jan 30, 2023 at 22:37 | comment | added | Max Alekseyev | @Thoth: This is how we compute the odd part of a function with respect to $x_1$. | |
| Jan 30, 2023 at 21:02 | comment | added | Thoth | Sorry for my delayed comment. I am trying to understand the answer. It is mentioned that to eliminate even $a_1$ we consider the expansion $\frac{1}{2}(x_1 + x_2 + \dots + x_k)^{\ell} - \frac{1}{2}(-x_1 + x_2 + \dots + x_k)^{\ell}.$ I do not catch the intuition. Could you please provide some more details? | |
| Aug 25, 2011 at 14:30 | comment | added | Ira Gessel | 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. | |
| Aug 25, 2011 at 9:09 | comment | added | Gjergji Zaimi | Combinatorial interpretation: number of of walks of length $l$ joining two antipodal points in the $k$-dimensional cube. | |
| Aug 25, 2011 at 2:57 | vote | accept | Simon Rose | ||
| Aug 24, 2011 at 22:49 | history | edited | Max Alekseyev | CC BY-SA 3.0 |
added 79 characters in body
|
| Aug 24, 2011 at 22:44 | history | edited | Max Alekseyev | CC BY-SA 3.0 |
added 10 characters in body
|
| Aug 24, 2011 at 22:38 | history | answered | Max Alekseyev | CC BY-SA 3.0 |