Combinatorial proof for identity $\left(\!\!\binom{n\vphantom{1}}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right)$ (multiset coefficients)

Question

In class we have recently started using combinatorial proofs. I have tried this problem that our teacher has assigned as a "challenge". I understand how to receive the left hand side, but am struggling with the right. I do no see how the k is now on the top. I understand the use of the stars and bars technique but do not know how to apply it to this side. Any help would be highly appreciated. The problem reads:

Prove with a combinatorial proof: $$\left(\!\!\binom{n}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right)$$ where the notation means multiset choose.

Answer 1

Write both coefficients as binomial coefficients using the formula you linked to. Note that the two binomial coefficients express the same number despite having different lower arguments. Why is this? Can you prove this combinatorially? If so, composing the bijection you use in that proof with the two stars-and-bars bijections used to convert the multiset coefficients to binomial coefficients yields a bijection that affords a combinatorial proof of your equation.

Answer 2

Let $N$ be the number of ways to put $n-1$ red balls and $k$ blue balls into a row. Each such configuration can be regarded

(a) as an encoding of a multiset of cardinality $k$ on $\{1,2,\ldots,n\}$, using the $n-1$ red balls as separators,

and at the same time

(b) as an encoding of a multiset of cardinality $n-1$ on $\{1,2,\ldots, k+1\}$, using the $k$ blue balls as separators.