Convolution formula for multisets coefficients 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!
 A: 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!
A: 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.
