Simplify a sum with a product and multinomial coefficient

This is a follow-up question to my previous post, where I've got a great help! (I created a new one to avoid editing the original one). Can the following sum be simplified?

$$\sum_{\substack{k_1 + k_2 + \ldots + k_m &=& B \\ g_1 + g_2 + \ldots + g_m &=& W}} \left(\prod_{i=1}^{m}k_i\right) \cdot {B \choose k_1, k_2, \ldots k_m} \cdot {W \choose g_1, g_2, \ldots, g_m}$$ where $$B + W = n$$, and $$\forall_i: g_i = x - k_i$$, where $$x = \frac{n}{m}$$, and $$m\mid n$$ and $$k_i \geq 1$$

I tried to follow the steps suggested in my previous post, but I got stuck. For $$m=2$$ I've got the following $$\sum_{\substack{k_1 + k_2 &=& B \\ k_1, k_2 &\geq& 0}} k_1 \cdot k_2 \cdot {B \choose k_1, k_2} \cdot {2N - B \choose N-k_1, N-k_2} \\ = \sum_{\substack{k_1 + k_2 &=& B \\ k_1, k_2 &\geq& 0}} k_2 \cdot {B \choose k_1-1} \cdot {2N - B \choose N-k_1, N-k_2} \\ = \sum_{k_1 = 0}^B \left(B-k_1 \right) \cdot {B \choose k_1-1} \cdot {2N - B \choose N-k_1} \\$$ From the previous post I know how to handle the binomial coefficients, but I'm not sure what can I do now with the $$B-k_1$$ factor inside the sum?

We have $$S = \sum\limits_{\left\{ {\matrix{ {k_{\,1} + k_{\,2} + \, \ldots + \,k_{\,m} = B} \cr {g_{\,1} + g_{\,2} + \, \ldots + \,g_{\,m} = W} \cr } } \right.} {\left( {\prod\limits_{i = 1}^m {k_{\,i} } } \right) \left( \matrix{ B \cr k_{\,1} ,\,k_{\,2} ,\, \ldots ,\,k_{\,m} \cr} \right) \left( \matrix{W \cr g_{\,1} ,\,g_{\,2} ,\, \ldots ,\,g_{\,m} \cr} \right)}$$

plus the added conditions $$\left\{ \matrix{ B + W = n \hfill \cr g_{\,i} = x - k_{\,i} \hfill \cr 1 \le k_{\,i} \hfill \cr} \right.$$ Leave apart for the moment the fact that $$x=n/m, \; m | n$$.
Because of the product, we can consider $$0 \le ki$$, and for the multinomial not to be null it shall be $$0 \le g_i$$.

Thus the set of conditions becomes (if I understood them properly) \eqalign{ & \left\{ {\matrix{ {0\, \le \,k_{\,i} ,\;g_{\,i} \, \le \,x} \cr {g_{\,i} = x - k_{\,i} } \cr {k_{\,1} + k_{\,2} + \, \ldots + \,k_{\,m} = B} \cr {g_{\,1} + g_{\,2} + \, \ldots + \,g_{\,m} = W} \cr } } \right.\quad \Rightarrow \cr & \Rightarrow \quad \left\{ {\matrix{ {0\, \le \,k_{\,i} ,\;g_{\,i} \, \le \,x} \cr {g_{\,i} = x - k_{\,i} } \cr {k_{\,1} + k_{\,2} + \, \ldots + \,k_{\,m} = B} \cr {\left( {x - k_{\,1} } \right) + \left( {x - k_{\,2} } \right) + \, \ldots + \,\left( {x - k_{\,m} } \right) = W} \cr } } \right.\quad \Rightarrow \cr & \Rightarrow \quad \left\{ {\matrix{ {0\, \le \,k_{\,i} ,\;g_{\,i} \, \le \,x} \cr {g_{\,i} = x - k_{\,i} } \cr {k_{\,1} + k_{\,2} + \, \ldots + \,k_{\,m} = B} \cr {W + B = mx = n} \cr } } \right. \cr}

Under these conditions the summand can be rewritten as \eqalign{ & \left( {\prod\limits_{i = 1}^m {k_{\,i} } } \right) \left( \matrix{ B \cr k_{\,1} ,\,k_{\,2} ,\, \ldots ,\,k_{\,m} \cr} \right) \left( \matrix{ W \cr g_{\,1} ,\,g_{\,2} ,\, \ldots ,\,g_{\,m} \cr} \right) = \cr & = \left( {\prod\limits_{i = 1}^m {k_{\,i} } } \right){{B!} \over {k_{\,1} !\,k_{\,2} !\, \cdots \,k_{\,m} !}} {{\left( {mx - B} \right)!} \over {\left( {x - k_{\,1} } \right)!\,\left( {x - k_{\,2} } \right)!\, \cdots \,\left( {x - k_{\,m} } \right)!}} = \cr & = {{B!\left( {mx - B} \right)!} \over {\left( {x!} \right)^{\,m} }} \left( {\prod\limits_{i = 1}^m {k_{\,i} } } \right){{x!} \over {k_{\,1} !\,\left( {x - k_{\,1} } \right)!}} {{x!} \over {k_{\,2} !\,\left( {x - k_{\,2} } \right)!}} \cdots {{x!} \over {k_{\,m} !\,\left( {x - k_{\,m} } \right)!}} = \cr & = {{B!\left( {mx - B} \right)!} \over {\left( {x!} \right)^{\,m} }} \prod\limits_{i = 1}^m {{{x\left( {x - 1} \right)^{\,\underline {\,k_{\,i} - 1\,} } } \over {\left( {k_{\,i} - 1} \right)!\,}}} = \cr & = {{B!\left( {mx - B} \right)!} \over {\left( {\left( {x - 1} \right)!} \right)^{\,m} }} \prod\limits_{i = 1}^m {{{\left( {x - 1} \right)^{\,\underline {\,k_{\,i} - 1\,} } } \over {\left( {k_{\,i} - 1} \right)!\,}}} = {{B!\left( {mx - B} \right)!} \over {\left( {\left( {x - 1} \right)!} \right)^{\,m} }} \prod\limits_{i = 1}^m {\left( \matrix{ x - 1 \cr k_{\,i} - 1 \cr} \right)} \cr} so that the sum becomes \eqalign{ & S(B,m,x)\quad \left| {\;1\, \le mx \le B} \right.\quad = \cr & = \sum\limits_{\left\{ {\matrix{ {0\, \le \,k_{\,i} ,\;g_{\,i} \, \le \,x} \cr {g_{\,i} = x - k_{\,i} } \cr {k_{\,1} + k_{\,2} + \, \ldots + \,k_{\,m} = B} \cr {g_{\,1} + g_{\,2} + \, \ldots + \,g_{\,m} = W} \cr } } \right.} {\left( {\prod\limits_{i = 1}^m {k_{\,i} } } \right) \left( \matrix{B \cr k_{\,1} ,\,k_{\,2} ,\, \ldots ,\,k_{\,m} \cr} \right) \left( \matrix{ W \cr g_{\,1} ,\,g_{\,2} ,\, \ldots ,\,g_{\,m} \cr} \right)} = \cr & = {{B!\left( {mx - B} \right)!} \over {\left( {\left( {x - 1} \right)!} \right)^{\,m} }} \sum\limits_{\left\{ {\matrix{ {\left( {1\, \le } \right)\,k_{\,i} \,\left( { \le \,x} \right)} \cr {k_{\,1} + k_{\,2} + \, \ldots + \,k_{\,m} = B} \cr } } \right.} {\prod\limits_{i = 1}^m {\left( \matrix{ x - 1 \cr k_{\,i} - 1 \cr} \right)} } = \cr & = {{B!\left( {mx - B} \right)!} \over {\left( {\left( {x - 1} \right)!} \right)^{\,m} }} \sum\limits_{\left\{ {\matrix{ {\left( {0\, \le } \right)\,j_{\,i} \,\left( { \le \,x - 1} \right)} \cr {j_{\,1} + j_{\,2} + \, \ldots + \,j_{\,m} = B - m} \cr } } \right.} {\prod\limits_{i = 1}^m {\left( \matrix{ x - 1 \cr j_{\,i} \cr} \right)} } \cr}

Now, since \eqalign{ & \left( {\left( {1 + z} \right)^{x - 1} } \right)^{\,m} = \prod\limits_{i = 1}^m {\left( {\sum\limits_{\left( {0\, \le } \right)\,j_{\,i} \,\left( { \le \,x - 1} \right)} {\left( \matrix{ x - 1 \cr j_{\,i} \cr} \right)z^{\,j_{\,i} } } } \right)} = \cr & = \sum\limits_{0\, \le \,s\, \le \,m\,\left( {x - 1} \right)} {\sum\limits_{\left\{ {\matrix{ {\left( {0\, \le } \right)\,j_{\,i} \,\left( { \le \,x - 1} \right)} \cr {j_{\,1} + j_{\,2} + \, \ldots + \,j_{\,m} = \,s} \cr } } \right.} {\left( {\prod\limits_{i = 1}^m {\left( \matrix{ x - 1 \cr j_{\,i} \cr} \right)} } \right)z^{\,s} } } \cr} we conclude that \bbox[lightyellow] { \eqalign{ & S(B,m,x)\quad \left| {\;1\, \le mx \le B} \right.\quad = \cr & = {{B!\left( {mx - B} \right)!} \over {\left( {\left( {x - 1} \right)!} \right)^{\,m} }} \;\;\left[ {z^{\,B - m} } \right]\left( {1 + z} \right)^{m\left( {x - 1} \right)} = \cr & = {{B!\left( {mx - B} \right)!} \over {\left( {\left( {x - 1} \right)!} \right)^{\,m} }} \;\;\left( \matrix{ m\left( {x - 1} \right) \cr B - m \cr} \right) = \cr & = {{B!\left( {mx - B} \right)!} \over {\left( {\left( {x - 1} \right)!} \right)^{\,m} }} \;{{\left( {m\left( {x - 1} \right)} \right)!} \over {\left( {B - m} \right)!\left( {mx - B} \right)!}}\; = \cr & = {{B!} \over {\left( {B - m} \right)!}}\; {{\left( {m\left( {x - 1} \right)} \right)!} \over {\left( {\left( {x - 1} \right)!} \right)^{\,m} }}\; = \left( \matrix{ B \cr m \cr} \right)\; {{m!\left( {m\left( {x - 1} \right)} \right)!} \over {\left( {\left( {x - 1} \right)!} \right)^{\,m} }} \cr} }

Consider the following simple case \eqalign{ & \left( {1 + z} \right)^a \left( {1 + z} \right)^a = \left( {\sum\limits_{k_1 } {\left( \matrix{ a \cr k_1 \cr} \right)z^{k_1 } } } \right) \left( {\sum\limits_{k_2 } {\left( \matrix{ a \cr k_2 \cr} \right)z^{k_2 } } } \right) = \cr & = \prod\limits_{i = 1}^2 {\left( {\sum\limits_{k_i } {\left( \matrix{a \cr k_i \cr} \right)z^{k_i } } } \right)} = \cr & = \sum\limits_{k_1 } {\sum\limits_{k_2 } {\left( \matrix{ a \cr k_1 \cr} \right)\left( \matrix{ a \cr k_2 \cr} \right)z^{k_1 + k_2 } } } = \sum\limits_s {\sum\limits_{k_1 + k_2 = s} {\left( \matrix{a \cr k_1 \cr} \right)\left( \matrix{a \cr k_2 \cr} \right)z^s } } = \cr & = \sum\limits_s {\left( {\sum\limits_{k_1 + k_2 = s} {\left( {\prod\limits_{i = 1}^2 {\left( \matrix{ a \cr k_i \cr} \right)} } \right)} } \right)z^s } = \sum\limits_s {\left( \matrix{ 2a \cr s \cr} \right)z^s } \cr} which implies $$\sum\limits_{k_1 + k_2 = s} {\left( {\prod\limits_{i = 1}^2 {\left( \matrix{a \cr k_i \cr} \right)} } \right)} = \left( \matrix{ 2a \cr s \cr} \right)$$ and which is just the Vandermonde convolution.

• It seems you don't properly respect the relationship between $g_i$ and $k_i$. You might want to check OP's referenced post. Mar 9, 2021 at 9:03
• @MarkusScheuer: Oops, thanks, I mislooked them. I recasted my answer considering them Mar 9, 2021 at 16:16
• I added a note about: is it clear ? Mar 9, 2021 at 19:29
• @GCab: I've added a note showing that our answers coincide. Good work! (+1) Mar 10, 2021 at 7:19
• @MarkusScheuer: it's always excellent to have a double check ! (+1) to your work as well. Mar 10, 2021 at 14:34

We assume positive integers $$m,n\geq 2$$. Since $$m\mid n$$ we know that $$n=Nm$$ is a multiple of $$m$$ with $$N\geq 1$$. This way we can write $$W=Nm-B$$ and $$x=N$$. We show by induction of $$m$$ that for all $$N\geq 1, m\leq B\leq Nm$$ the following is valid:

\begin{align*} \color{blue}{\sum_{\substack{k_1+\cdots+k_m=B\\k_1,\ldots,k_m\geq 0}} \binom{B}{k_1,\ldots,k_m}\binom{mN-B}{N-k_1,\ldots,N-k_m}=B^{\underline{m}}\prod_{q=2}^m\binom{q(N-1)}{N-1}}\tag{1} \end{align*}

with $$B^{\underline{m}}=B(B-1)\cdots(B-m+1)$$ the falling factorial.

Base step: $$m=2$$

We obtain for natural numbers $$B,N$$ with $$2\leq B\leq 2N$$: \begin{align*} \color{blue}{\sum_{\substack{k_1+k_2=B\\k_1,k_2\geq 0}}}&\color{blue}{k_1k_2\binom{B}{k_1,k_2}\binom{2N-B}{N-k_1,N-k_2}}\\ &=\sum_{k_1=0}^{B}k_1\left(B-k_1\right)\binom{B}{k_1}\binom{2N-B}{N-k_1}\tag{1}\\ &=B\sum_{k_1=1}^{B-1}\left(B-k_1\right)\binom{B-1}{B-k_1}\binom{2N-B}{N-k_1}\tag{2}\\ &=B(B-1)\sum_{k_1=1}^{B-1}\binom{B-2}{k_1-1}\binom{2N-B}{N-k_1}\tag{3}\\ &=B^{\underline{2}}\sum_{k_1=0}^{B-2}\binom{B-2}{k_1}[z^{N-k_1-1}](1+z)^{2N-B}\tag{4}\\ &=B^{\underline{2}}[z^{N-1}](1+z)^{2N-B}(1+z)^{B-2}\tag{5}\\ &\,\,\color{blue}{=B^{\underline{2}}\binom{2(N-1)}{N-1}}\tag{6} \end{align*}

Comment:

• In (1) we write the multinomial as binomial coefficients, substituting $$k_2=B-k_1$$.

• In (2) we use the binomial identity $$\binom{p}{q}=\frac{p}{q}\binom{p-1}{p-q}$$ and we skip the indices $$k_1=0$$ and $$k_1=B$$ which do not contribute to the sum.

• In (3) we use again $$\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}=\frac{p}{q}\binom{p-1}{p-q}$$ as in (2) and (3).

• In (4) we shift the index $$k_1$$ by one to start with $$k_1=0$$. We use the coefficient of operator $$[z^N]$$ to denote the coefficient of $$z^N$$ of a series.

• In (5) we apply the rule $$[z^{p-q}]A(z)=[z^p]z^qA(z)$$ and we apply the binomial theorem.

• In (6) we select the coefficient of $$z^{N-1}$$.

Induction hypothesis: $$m=M$$

We assume the validity of \begin{align*} \color{blue}{\sum_{\substack{k_1+\cdots+k_M=B\\k_1,\ldots,k_M\geq 0}} \binom{B}{k_1,\ldots,k_M}\binom{MN-B}{N-k_1,\ldots,N-k_M}=B^{\underline{M}}\prod_{q=2}^M\binom{q(N-1)}{N-1}}\tag{7} \end{align*}

Induction step: $$m=M+1$$

We have to show \begin{align*} &\color{blue}{\sum_{\substack{k_1+\cdots+k_{M+1}=B\\k_1,\ldots,k_{M+1}\geq 0}} \binom{B}{k_1,\ldots,k_{M+1}}\binom{(M+1)N-B}{N-k_1,\ldots,N-k_{M+1}}}\\ &\qquad\qquad\color{blue}{=B^{\underline{{M+1}}}\prod_{q=2}^{M+1}\binom{q(N-1)}{N-1}}\tag{8} \end{align*}

We obtain for $$M\geq 2$$: \begin{align*} &\color{blue}{\sum_{\substack{k_1+\cdots+k_{M+1}=B\\k_1,\ldots,k_{M+1}\geq 0}} \binom{B}{k_1,\ldots,k_{M+1}}\binom{(M+1)N-B}{N-k_1,\ldots,N-k_{M+1}}}\\ &\qquad=\sum_{k_{M+1}=1}^{B-1}k_{M+1}\frac{B!}{k_{M+1}!(B-k_{M+1})!}\,\frac{((M+1)N-B)!}{(N-k_{M+1})!(MN-(B-k_{M+1}))!}\\ &\qquad\qquad\cdot\sum_{\substack{k_1+\cdots+k_{M}=B-k_{M+1}\\k_1,\ldots,k_{M}\geq 0}} \binom{B-k_{M+1}}{k_1,\ldots,k_{M}}\binom{MN-(B-k_{M+1})}{N-k_1,\ldots,N-k_{M}}\tag{9}\\ &=B\sum_{k_{M+1}=1}^{B-1}\binom{B-1}{B-k_{M+1}}\binom{(M+1)N-B}{N-k_{M+1}}\\ &\qquad\qquad\cdot\left(B-k_{M+1}\right)^{\underline{M}}\prod_{q=2}^M\binom{q(N-1)}{q}\tag{10}\\ &=B\sum_{k_{M+1}=1}^{B-M+1}\frac{(B-1)^{\underline{M}}}{(B-k_{M+1})^{\underline{M}}}\binom{B-M-1}{B-k_{M+1}-M+1}\binom{(M+1)N-B}{N-k_{M+1}}\\ &\qquad\qquad\cdot\left(B-k_{M+1}\right)^{\underline{M}}\prod_{q=2}^M\binom{q(N-1)}{q}\\ &=B^{\underline{M+1}}\prod_{q=2}^M\binom{q(N-1)}{N-1} \sum_{k_{M+1}=0}^{B-M}\binom{B-M-1}{k_{M+1}}\binom{(M+1)N-B}{N-k_{M+1}-1}\\ &=B^{\underline{M+1}}\prod_{q=2}^M\binom{q(N-1)}{N-1} \sum_{k_{M+1}=0}^{B-M}\binom{B-M-1}{k_{M+1}}[z^{N-k_{M+1}-1}](1+z)^{(M+1)N-B}\\ &=B^{\underline{M+1}}\prod_{q=2}^M\binom{q(N-1)}{N-1} [z^{N-1}](1+z)^{(M+1)N-B}(1+z)^{B-M-1}\\ &=B^{\underline{M+1}}\prod_{q=2}^M\binom{q(N-1)}{N-1}\binom{(M+1)N-M-1}{N-1}\\ &\,\,\color{blue}{=B^{\underline{M+1}}\prod_{q=2}^{M+1}\binom{q(N-1)}{N-1}}\\ \end{align*} in accordance with (8) and the claim follows.

Comment:

• In (9) we separate $$k_{M+1}$$ and expand to get binomial coefficients in the next step.

• In (10) we apply the induction hypothesis.

Note: We obtain from (1): \begin{align*} \color{blue}{B^{\underline{m}}\prod_{q=2}^m\binom{q(N-1)}{N-1}} &=B^{\underline{m}}\cdot\frac{\prod_{q=2}^m\left(q(N-1)\right)!}{\prod_{q=2}^m(N-1)!\prod_{q=2}^m\left((q-1)(N-1)\right)!}\\ &=B^{\underline{m}}\cdot\frac{\prod_{q=2}^m\left(q(N-1)\right)!}{\left((N-1)!\right)^{m-1}\prod_{q=1}^{m-1}\left(q(N-1)\right)!}\\ &=B^{\underline{m}}\cdot\frac{\left(m(N-1)\right)!}{\left((N-1)!\right)^{m}}\\ &\,\,\color{blue}{=\binom{B}{m}\frac{m!\left(m(N-1)\right)!}{\left((N-1)!\right)^{m}}} \end{align*} in accordance with the answer from @GCab.

• Hi, Markus, something doesn't "run" in your answer, or maybe I did not catch OP question ? Mar 9, 2021 at 0:08
• @Markus Thanks a lot! Do you mind adding the final general form (for any 𝑚) so that I can accept the answer? Mar 9, 2021 at 14:03
• @SugerBoy: Final form added. Mar 9, 2021 at 22:36
• Big thank you to both of you! I've learned a lot from your solutions! Mar 10, 2021 at 17:49
• @SugerBoy: You're welcome! :-) Mar 10, 2021 at 18:03