Fórmula de convolución para coeficientes multisectas

Question

He estado tratando de resolver el siguiente problema:

(a) Dar dos pruebas de coeficiente binomial identidad, llama la fórmula de la convolución, $\sum_{j = 0}^k \binom{m}{j}\binom{n}{k - j} = \binom{m + n}{k}$.

(b) Descubrir y probar un análogo de identidad para el conjunto múltiple coeficientes de $\bigg(\binom{n}{k}\bigg)$

La parte (a) no es difícil de probar, ya que $\binom{n + m}{k}$ representa todas las formas en que podemos formar un grupo con $k$ miembros $m$ hombres y $n$ mujeres. El lado izquierdo es contar exactamente la misma fijación previamente el número de mujeres u hombres. Pero no sé cómo resolver inc (b). Por favor una sugerencia sería increíble! Gracias de antemano!

Answer 1

Aviso de que la misma fórmula es válida para el caso del conjunto múltiple de los coeficientes. Por lo tanto,

$\sum_{j = 0}^k \left(\!\left({m\atop j}\right)\!\right)\left(\!\left({n\atop k - j}\right)\!\right) = \left(\!\left({m + n\atop k}\right)\!\right)$.

Como se hizo para el caso de los coeficientes binomiales, vamos a suponer que tenemos $m$ hombres y $n$ mujeres. Digamos que tenemos que elegir el $k$ de las personas de este conjunto, y cada persona seleccionada se va a ganar un Premio Nobel. Por supuesto, una persona puede ganar más de un Premio Nobel. Claramente, el lado derecho cuenta todas las formas en que podemos hacer esto. Y el lado derecho de la cuenta de los mismos fenómenos, ya que si hemos determinado previamente que la $j$ $k$ premios hemos van a ser recibidos por las mujeres, entonces tenemos que elegir el otro $k - j$ a los destinatarios de los hombres del grupo. Esta es una combinatoria de la prueba. Ahora usted puede encontrar uno con funciones de generación!

Answer 2

He aquí otra prueba basada en la generación de funciones. Tenga en cuenta que $$ \frac{1}{(1-x)^n}=(1+x+x^2+\dotsb)^n= \sum_{x_1+x_2+\dotsb+x_n=k; \,x_i\geq0}x^{x_1+x_2+\dotsb+x_n} =\sum_{k=0}^\infty\left(\!\!{n\elegir k}\!\!\right)x^k. $$ Entonces $$ \sum_{k=0}^\infty\left(\!\!{m+n\elegir k}\!\!\right)x^k=\frac{1}{(1-x)^{m+n}}=\frac{1}{(1-x)^{m}}\frac{1}{(1-x)^{n}} =\left(\sum_{k=0}^\infty\left(\!\!{m\elegir k}\!\!\right)x^k\right)\left(\sum_{k=0}^\infty\left(\!\!{n\elegir k}\!\!\right)x^k\right). $$ Multiplicando el producto en el lado derecho (de Cauchy producto de dos series), llegamos a que $$ \sum_{k=0}^\infty\left(\!\!{m+n\elegir k}\!\!\right)x^k= \sum_{k=0}^\infty\left( \sum_{j = 0}^k \left(\!\!{m\elegir j}\!\!\right) \left(\!\!{n\elegir k-j}\!\!\right) \right)x^k $$ y el resultado de la siguiente manera.