# 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?

• Also refer to the follow up post Commented Mar 11, 2021 at 9:55

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.

• Thanks for your answer! I am a bit confused why did you substitute $g_i$ with $n-k_i$ instead of $x - k_i$? Commented Mar 5, 2021 at 11:34
• I'm a bit confused, if I am given that $x = \frac{n}{m}$ how can I replace it to be $x = \frac{m \cdot n}{m}$? The same with $W = n - B$ to turn it into $W = mn - B$? Commented Mar 5, 2021 at 16:04
• Yes, indeed I agree that $n$ is a multiple of $m$ but shouldn't we say that then $n = y \cdot m$, where $y$ is some positive integer? Commented Mar 5, 2021 at 16:43
• SugarBoy: You're welcome! You might find this answer helpful. A further very simple example and slightly more complex. Commented Mar 8, 2021 at 15:37
• @SugerBoy: You're welcome!. Good to see the information is useful. :-) Commented Mar 8, 2021 at 16:02