Combinatorial proof of multiset coefficient identity: $\left(\!\left({n\atop k}\right)\!\right)= \left(\!\!\left({k+1\atop n-1}\right)\!\!\right)$

Question

I would like a combinatorial proof of this identity for multiset coefficients:

$$\left(\!\left({n\atop k}\right)\!\right) = \left(\!\!\left({k+1\atop n-1}\right)\!\!\right)$$

It is not famaliar to me. Please help.

Answer 1

$$\left(\kern-0.5em{n\choose k}\kern-0.5em\right)={n+k-1\choose k}={n+k-1\choose n-1} ={(k+1)+(n-1)-1\choose n-1}=\left(\kern-0.5em{k+1\choose n-1}\kern-0.5em\right)$$

Here's a translation to a combinatorical argument: A multiset of $k$ elements taken from $\{1,\ldots,n\}$ is the same as a non-decreasing seequnce $(a_i)_{i=1}^k$ with $$1\le a_1\le \ldots\le a_k\le n.$$ Then the numbers $b_i:=a_i+i-1$ are a strictly increasing sequence with $$1\le b_1<b_2<\ldots <b_k\le n+k-1.$$ Form a strictly increasing sequence from the numbers $\in\{1,\ldots,n+k-1\}$ that do not occur in the sequence of $(b_i)_{i=1} k$. That is a sequence $(c_i)_{i=1}^{n-1}$ with $$1\le c_1<c_2<\ldots<c_{n-1}\le n+k-1.$$ Let $d_i=c_i-i+1$. That is a non-decreasing sequence $(d_i)_{i=1}^{n-1}$ with $$1\le d_1\le d_2\le\ldots\le d_{n-1}\le k+1$$

Note that the same construction applied to $(d_i)_{i=1}^{n-1}$ gives us our original $(a_i)_{i=1}^k$ back and vice versa. In other words, we have exhibited a bijection between the sets of multisets in question.

Answer 2

A Combinatorial Proof

The number of ways of selecting a total of $k$ objects out of $n$ types of objects, with unrestricted repetition of each type is $\displaystyle\left(\kern-0.5em\binom{n}{k}\kern-0.5em\right)$.

Consider a collection of $k$ identical marbles arranged in a row, representing the total of $k$ objects to be selected. In order to indicate the number of objects of each type (out of the $n$ types), we can partition the $k$ marbles by inserting $n - 1$ identical "dividers" in various places between them, as follows. The number of marbles to the left of the first divider is the number of objects of the first type to be selected; the number of objects between the first and second dividers indicates the objects of the second type; and so on. How many such arrangements are there? As many as the number of ways of inserting the dividers in the various places between the marbles. We may insert some dividers before the first marble, to indicate a selection of zero objects of the first few types. Similarly, we may insert some dividers after the last marble. Thus, there are totally $k + 1$ spaces in which the $n - 1$ dividers could be inserted, and any number can be inserted in the same space. Therefore, the total number of such arrangements is the number of ways of selecting $n - 1$ out of $k + 1$ spaces, with unrestricted repetition — i.e., $\displaystyle\left(\kern-0.5em\binom{k+1}{n-1}\kern-0.5em\right)$.

There is a one-to-one correspondence between the arrangements of this type and the unrestricted selections of $k$ objects out of $n$ types. Therefore, \begin{equation*} \boxed{\left(\kern-0.5em\binom{n}{k}\kern-0.5em\right) = \left(\kern-0.5em\binom{k+1}{n-1}\kern-0.5em\right)} \end{equation*}