Combinatorial proof (multi choose)

Question

I'm struggling to explain why these two sides are equal in a non algebraic way. Basically I'm looking for a combinatorial proof of why these sides are equal. I know they are equal by algebra.

N "multi choose" K = K+1 "multi choose" N-1

Any ideas?

Answer 1

The most common notation for $n$ multichoose $k$ is $$\left(\!\!\binom{n}k\!\!\right)\;;$$ it counts the multisets of cardinality $k$ that can be made from a set of $n$ distinct elements. Similarly, $$\left(\!\!\binom{k+1}{n-1}\!\!\right)$$ is the number of multisets of cardinality $n-1$ that can be made from a set of $k+1$ distinct elements.

Consider a $k$-element multiset made from the set $\{1,\ldots,n\}$; we can represent it schematically as a string of $k$ $0$s and $n-1$ $1$s, the $i$-th $1$ indicating the break between $0$s representing copies of $i$ and $0$s representing copies of $i+1$. For instance, if $n=5$ and $k=8$, the multiset $$\{\!\{2,2,4,4,4,4,4,5\}\!\}$$ can be represented by the string $$100110000010\;.$$ That is, there are no $1$s in the multiset, since there is nothing to the left of the first $1$ in the string; there are two $2$s in the multiset, since there are two $0$s between the first and second $1$s in the string; there are no $3$s in the multiset, because there are no $0$s between the second and third $1$s in the string; there are five $4$s in the multiset, because there are five $0$s between the third and fourth $1$s in the string; and there is one $5$ in the multiset, because there is one $0$ after the fourth $1$ in the string. It’s clear that each $k$-element multiset from $\{1,\ldots,n\}$ gives rise to a unique string of $k$ $0$s and $n-1$ $1$s in this way, and that each such string of $0$s and $1$s in turn describes a unique $k$-element multiset from $\{1,\ldots,n\}$.

However, we can reverse the rôles of $0$ and $1$: we can interpret the $0$s as dividers and the $1$s as counters. In that case we have $k$ dividers and $n-1$ counters. The $k$ dividers break the string into $k+1$ sections, so it represents an $(n-1)$-element multiset chosen from $\{1,\ldots,k+1\}$. The string above, for instance, corresponds to the multiset $$\{\!\{1,3,3,8\}\!\}\;.$$

Instead of reversing the rôles of $0$ and $1$, you can of course simply change each $0$ to a $1$ and each $1$ to a $0$ and keep the original interpretation; in the example that yields the string $011001111101$. This has one $0$ before the first $1$, so the multiset contains a single $1$. It has no $0$s between the first and second $1$s, so the multiset contains no $2$s. And so on.

Thus, the two possible interpretations of a string of $k$ $0$s and $n-1$ $1$s provide a natural bijection between $k$-element multisets chosen from $\{1,\ldots,n\}$ and $(n-1)$-element multisets chosen from $\{1,\ldots,k+1\}$, thereby giving a combinatorial proof that $$\left(\!\!\binom{n}k\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right)\;.$$