combinatorial proof of identity involving multisets

Question

I was wondering how to do a combinatorial proof of the following identity: ${n+k-1\choose k-1} = \sum_{j=0}^{\lfloor n/2\rfloor} {k\choose n-2j}{j+k-1\choose k-1}$?

The LHS is just the number of multisets of $k$ types and $n$ elements while the RHS seems to represent some sort of Cartesian product. I initially thought it was the number of ways to choose $n-2j$ types from $k$ types times the number of ways to make a multiset of $j$ elements of $k$ types, but I can't seem to derive a proper bijection from this.

Answer 1

I have $k$ boxes and $n$ balls. For some $j$ with $0\le j\le\lfloor n/2\rfloor$ I distribute $j$ balls amongst the boxes, and then I double the number of balls in each box; I can do this in $\binom{j+k-1}{k-1}$ ways. At that point I have $n-2j$ balls left, and I pick $n-2j$ boxes and place one of the remaining balls in each of these boxes; I can do this in $\binom{k}{n-2j}$ ways. I claim that each of the $\binom{n+k-1}{k-1}$ distributions of the $n$ balls amongst the $k$ boxes can be obtained in exactly one way through this procedure.

Specifically, take any distribution of the $n$ balls to the $k$ boxes. Let $A$ be the set of boxes containing an odd number of balls. If we remove one ball from each of these boxes, $n-|A|$ balls remain the $k$ boxes altogether, and the number remaining is even, say $2k$ for some $k$, where clearly $0\le k\le\lfloor n/2\rfloor$. Thus, $|A|=n-2k$, and this particular distribution is counted once in the term $j=k$. In general, the term $\binom{k}{n-2j}\binom{j+k-1}{k-1}$ counts the distributions that have $n-2j$ boxes containing an odd number of balls.