Simplifying the sum of a product of multinomial coefficients 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?
 A: 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*}

Base step: $m=2$
\begin{align*}
\color{blue}{\sum_{{k_1+k_2=B}\atop{k_1,k_2\geq 0}}}
&\color{blue}{\binom{B}{k_1,k_2}\binom{2N-B}{N-k_1,N-k_2}}\\
&=\sum_{k_1=0}^B\binom{B}{k_1}\binom{2N-B}{N-k_1}\tag{2}\\
&=\sum_{k_1=0}^B\binom{B}{k_1}[z^{N-k_1}](1+z)^{2N-B}\tag{3}\\
&=[z^N](1+z)^{2N-B}\sum_{k_1=0}^B\binom{B}{k_1}z^{k_1}\tag{4}\\
&=[z^N](1+z)^{2N-B}(1+z)^{B}\\
&=[z^N](1+z)^{2N}\\
&\,\,\color{blue}{=\binom{2N}{N}}\tag{5}
\end{align*}
in accordance with (1).

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

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}}=\prod_{q=2}^{M+1}\binom{qN}{N}}\tag{7}
\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}}}\color{blue}{\binom{B}{k_1,\ldots,k_{M+1}}\binom{(M+1)N-B}{N-k_1,\ldots,n-k_{M+1}}}\\
&\qquad=\sum_{{k_1+\cdots+k_{M+1}=B}\atop{k_1,\ldots,k_{M+1}\geq 0}}\frac{B!}{k_1!\cdots k_{M+1}!}\,\frac{\left((M+1)N-B\right)!}{\left(N-k_1\right)!\cdots\left(N-k_{M+1}\right)!}\tag{8}\\
&\qquad=\sum_{k_{M+1}=0}^B\frac{B!}{k_{M+1}!\left(B-k_{M+1}\right)!}\,
\frac{\left((M+1)N-B\right)!}{\left(N-k_{M+1}\right)!\left(MN-\left(B-k_{M+1}\right)\right)!}\\
&\qquad\quad\cdot\sum_{{k_1+\cdots+k_M=B-k_{M+1}}\atop{k_1,\ldots,k_{M}\geq 0}}\frac{\left(B-k_{M+1}\right)!}{k_1!\cdots k_{M}!}\,\frac{\left(MN-\left(B-k_{M+1}\right)\right)!}{\left(N-k_1\right)!\cdots\left(N-k_{M}\right)!}\tag{9}\\
&\qquad=\sum_{k_{M+1}=0}^B\binom{B}{k_{M+1}}\,
\binom{(M+1)N-B}{N-k_{M+1}}\\
&\qquad\quad\cdot\sum_{{k_1+\cdots+k_M=B-k_{M+1}}\atop{k_1,\ldots,k_{M}\geq 0}}
\binom{B-k_{M+1}}{k_1,\ldots, k_{M}}\,\binom{MN-\left(B-k_{M+1}\right)}{N-k_1,\ldots,N-k_{M}}\tag{10}\\
&\qquad=\prod_{q=2}^M\binom{qN}{N}\sum_{k_{M+1}=0}^B\binom{B}{k_{M+1}}
[z^{N-k_{M+1}}](1+z)^{(M+1)N-B}\tag{11}\\
&\qquad=[z^{N}](1+z)^{(M+1)N-B}\prod_{q=2}^M\binom{qN}{N}\sum_{k_{M+1}=0}^B\binom{B}{k_{M+1}}z^{k_{M+1}}\\
&\qquad=[z^{N}](1+z)^{(M+1)N-B}\prod_{q=2}^M\binom{qN}{N}(1+z)^B\\
&\qquad=[z^{N}](1+z)^{(M+1)N}\prod_{q=2}^M\binom{qN}{N}\\
&\qquad=\binom{(M+1)N}{N}\prod_{q=2}^M\binom{qN}{N}\\
&\qquad\,\,\color{blue}{=\prod_{q=2}^{M+1}\binom{qN}{N}}
\end{align*}
in accordance with (7) and the claim follows.

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.
