Simplificación de la suma de un producto de coeficientes multinomiales

Question

Desde el teorema multinomial se cumple lo siguiente

$$ \sum_{k_1 + k_2 + \ldots + k_m=n} {n \choose k_1, k_2, \ldots, k_m} = m^n $$

Tengo la siguiente suma $$ \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} $$ donde $B + W = n$ y $\forall_i: g_i = x - k_i$ donde $x = \frac{n}{m}$ y $m\mid n$ y $k_i \geq 1$

¿Puede simplificarse esta suma como la original?

Answer 1

Suponemos números enteros positivos $m,n\geq 2$ . Desde $m\mid n$ sabemos que $n=Nm$ es múltiplo de $m$ con $N\geq 1$ . De esta forma podemos escribir $W=Nm-B$ y $x=N$ . Demostramos por inducción de $m$ que para todos $N\geq 1, m\leq B\leq Nm$ lo siguiente es válido:

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

Paso básico: $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*} de acuerdo con (1).

Comentario:

• En (2) escribimos la multinomial como coeficientes binomiales y sustituimos $k_2 = B-k_1$ .

• En (3) utilizamos el coeficiente de operador $[z^N]$ para denotar el coeficiente de $z^N$ de una serie.

• En (4) aplicamos la regla $[z^{p-q}]A(z)=[z^p]z^qA(z)$ .

• En (5) seleccionamos el coeficiente de $z^{N}$ .

Hipótesis de inducción: $m=M$

Asumimos la validez de \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*}

Paso de inducción: $m=M+1$

Tenemos que demostrar \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*}

Obtenemos para $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*} de acuerdo con (7) y la reivindicación sigue.

Comentario:

• En (8) escribimos los coeficientes multinomiales utilizando factoriales.

• En (9) separamos la suma del sumando $k_{M+1}$ como preparación para aplicar la hipótesis de inducción. Ampliamos con $\left(B-k_{M+1}\right)!$ y $\left(MN-\left(B-k_{M+1}\right)\right)!$ para escribir la expresión con coeficientes binomiales y multinomiales.

• En (10) escribimos la expresión utilizando coeficientes binomiales y multinomiales.

• En (11) aplicamos la hipótesis de inducción. También utilizamos la coeficiente de operador de $[z^N]$ para denotar el coeficiente de $z^N$ de una serie.

• En las líneas siguientes utilizamos las mismas técnicas que en el paso base.