# Give a combinatorial proof of $\left(\!\!\binom{n}{k - n}\!\!\right) = {k - 1 \choose k - n}$

Coming up with a question whose answer is $\left(\!\!\binom{n}{k - n}\!\!\right)$ is easy: how many ways are there to create a $k$-multiset from $[n]$ such that each element in $[n]$ appears at least once? This is analogous to the question: how many ways are there to distribute $k$ identical objects to $n$ distinct recipients such that each recipient receives at least one object? You first distribute $k$ objects, then you are left to count the number of $(k - n)$-multisets from $[n]$. I get that.

Now coming up with a different way to answer these questions, namely with ${k - 1 \choose k - n}$, is where I'm struggling. I understand that you must first distribute $n$ objects to each recipient in $[n]$. Then you are left with $k - n$ objects to distribute. I don't know how to get to ${k - 1 \choose k - n}$.

Note: For those of you unfamiliar with the double parens notation, $\left(\!\!\binom{n}{k}\!\!\right)$, this denotes a $k$-multiset (or multichoose) taken from $[n]$. Examples of a $3$-multisets taken from [5] are $(1, 1, 1)$, $(3, 3, 4)$, $(1, 2, 3)$...

• what does this double bracket notation means?? I do not even know how to right it in latex. – user265328 Sep 25 '15 at 16:42

It’s a basic stars and bars setup. After distributing $n$ objects, one to each of $n$ recipients, you have $k-n$ objects to distribute arbitrarily to the $n$ recipients. If you line the objects by recipient, placing dividers between those for one recipient and those for the next, you have a total of $(k-n)+n=k$ entities, $k-n$ of which are objects.
• In the first line, should it be "After distributing $n$ objects..."? – James Pak Sep 25 '15 at 17:13