In this exercise we will prove Theorem $2$ by setting up a one-to-one correspondence between the set of $r$-combinations with repetition allowed of $S = \{1, 2, 3,\dots,n\}$ and the set of $r$-combinations of the set $T = \{1, 2, 3,\dots n + r − 1\}.$
- Arrange the elements in an $r$-combination, with repetition allowed, of $S$ into an increasing sequence $x_{1} \leq x_{2} \leq \dots \leq x_{r}.$ Show that the sequence formed by adding $k − 1$ to the $k^{\text{th}}$ term is strictly increasing. Conclude that this sequence is made up of $r$ distinct elements from $T.$
- Show that the procedure described in $(A)$ defines a one-to-one correspondence between the set of $r$-combinations, with repetition allowed, of $S$ and the $r$-combinations of $T.$ [Hint: Show the correspondence can be reversed by associating to the $r$-combination $\{x_{1}, x_{2},\dots,x_{r}\}$ of $T,$ with $1 \leq x_{1} < x_{2} <\dots < x_{r} \leq n + r − 1,$ the $r$-combination with repetition allowed from $S,$ formed by subtracting $k − 1$ from the $k^{\text{th}}$ element.]
- Conclude that there are $C(n + r − 1,r)\:\: r$-combinations with repetition allowed from a set with n elements.
