Simplify a sum with a product and multinomial coefficient

Question

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?

Answer 1

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

--- in reply to your comment ---

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.

Answer 2

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.