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?
Best Answer
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.