binomial-coefficientsmultinomial-coefficientsmultinomial-theoremsummation
From the multinomial theorem the following holds
$$
\sum_{k_1 + k_2 + \ldots + k_m=n} {n \choose k_1, k_2, \ldots, k_m} = m^n
$$
I have the following sum
$$
\sum_{\substack{k_1 + k_2 + \ldots + k_m &=& B \\ g_1 + g_2 + \ldots + g_m &=& W}} {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$
Can this sum be simplified like the original one?
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.
When considering \begin{align*} \left(x_1+x_2+\cdots+x_n\right)^n \end{align*} we multiply $x_j$ with $t^j$ to track the index of the variable $x_j$. In the following we use the coefficient of operator $[t^k]$ to denote the coefficient of $t^k$ of a series $A(t)$ .
We show the following is valid for $n\geq 2$: \begin{align*} \color{blue}{[t^{2n-1}]\left(x_1t+x_2t^2+\cdots+x_nt^n\right)^n\Big|_{x_1=x_2=\cdots=x_n=1} =\binom{2n-2}{n-1}}\tag{1} \end{align*}
We obtain \begin{align*} \color{blue}{[t^{2n-1}]}&\color{blue}{\left(x_1t+x_2t^2+\cdots+x_nt^n\right)^n\Big|_{x_1=x_2=\cdots=x_n=1}}\\ &=[t^{2n-1}]\left(t+t^2+\cdots+t^n\right)^n\tag{2}\\ &=[t^{n-1}]\left(1+t+\cdots+t^{n-1}\right)^n\tag{3}\\ &=[t^{n-1}]\left(\frac{1-t^n}{1-t}\right)^n\tag{4}\\ &=[t^{n-1}]\frac{1}{\left(1-t\right)^n}\tag{5}\\ &=[t^{n-1}]\sum_{k=0}^{\infty}\binom{-n}{k}(-t)^k\tag{6}\\ &=\binom{-n}{n-1}(-1)^{n-1}\tag{7}\\ &\,\,\color{blue}{=\binom{2n-2}{n-1}}\tag{8} \end{align*}
Comment:
In (2) we evaluate the expression at $x_1=x_2=\cdots=x_n=1$.
In (3) we factor out $t^n$ and apply the rule $[t^{p-q}]A(t)=[t^p]t^qA(t)$.
In (4) we apply the finite geometric series formula.
In (5) we skip all terms in the numerator $\left(1-t^n\right)^n=\sum_{j=0}^n\binom{n}{j}(-t^n)^j$ besides the constant term $1$ as the other terms do not contribute to $[t^{n-1}]$.
In (6) we make a binomial series expansion.
In (7) we select the coefficient of $t^{n-1}$.
In (8) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.
Best Answer
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}=\prod_{q=2}^m\binom{qN}{N}}\tag{1} \end{align*}
Comment:
In (2) we write the multinomial as binomial coefficients and substitute $k_2 = B-k_1$.
In (3) we use the coefficient of operator $[z^N]$ to denote the coefficient of $z^N$ of a series.
In (4) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.
In (5) we select the coefficient of $z^{N}$.
Induction hypothesis: $m=M$
We assume the validity of \begin{align*} \color{blue}{\sum_{{k_1+\cdots+k_M=B}\atop{k_1,\ldots,k_M\geq 0}} \binom{B}{k_1,\ldots,k_M}\binom{MN-B}{N-k_1,\ldots,N-k_M}=\prod_{q=2}^M\binom{qN}{N}}\tag{6} \end{align*}
Comment:
In (8) we write the multinomial coefficients using factorials.
In (9) we separate the summation of the summand $k_{M+1}$ as preparation to apply the induction hypothesis. We expand with $\left(B-k_{M+1}\right)!$ and $\left(MN-\left(B-k_{M+1}\right)\right)!$ to write the expression with binomial and multinomial coefficients.
In (10) we write the expression using binomial and multinomial coefficients.
In (11) we apply the induction hypothesis. We also use the coefficient of operator of $[z^N]$ to denote the coefficient of $z^N$ of a series.
In the following lines we use the same techniques as in the base step.