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!

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!