Convolution formula for multisets coefficients

Question

I've been trying to solve the following problem:

(a) Give two proofs of the binomial coefficient identity, called the convolution formula, $\sum_{j = 0}^k \binom{m}{j}\binom{n}{k - j} = \binom{m + n}{k}$.

(b) Discover and prove an analogous identity for multiset coefficients $\bigg(\binom{n}{k}\bigg)$

Part (a) is not hard to prove since $\binom{n + m}{k}$ represents all the ways in which we can form a group with $k$ members with $m$ men and $n$ women. The left-hand side is counting exactly the same fixing previously the number of women or men. But I do not know how to solve incise (b). Please a hint would be awesome! Thanks in advance!

Answer 1

Notice that the same formula is valid for the case of multiset coefficients. Thus,

$\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)$.

As you did for the case with binomial coefficients, let's assume that we have $m$ men and $n$ women. Let's say that we need to choose $k$ persons from this set, and each person selected is going to win a Nobel Prize. Of course, a person could win more than one Nobel Prize. Clearly, the right-hand side counts all the ways in which we can do this. And the right-hand side counts the same phenomena since if we previously determined that $j$ out of the $k$ prizes we have are going to be received by women, then we have to choose the other $k - j$ recipients from the men group. This is a combinatorial proof. Now you can find one using generating functions!

Answer 2

Here is another proof based on generating functions. Note that $$ \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\choose k}\!\!\right)x^k. $$ Then $$ \sum_{k=0}^\infty\left(\!\!{m+n\choose 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\choose k}\!\!\right)x^k\right)\left(\sum_{k=0}^\infty\left(\!\!{n\choose k}\!\!\right)x^k\right). $$ Multiplying the product out on the right side (Cauchy product of two series) we get that $$ \sum_{k=0}^\infty\left(\!\!{m+n\choose k}\!\!\right)x^k= \sum_{k=0}^\infty\left( \sum_{j = 0}^k \left(\!\!{m\choose j}\!\!\right) \left(\!\!{n\choose k-j}\!\!\right) \right)x^k $$ and the result follows.