Simplifying the sum of a product of multinomial coefficients

Question

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?

Answer 1

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.