edited by
289 views
0 votes
0 votes

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\}.$

  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.$
  2. 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.]
  3. Conclude that there are $C(n + r − 1,r)\:\: r$-combinations with repetition allowed from a set with n elements.
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4
admin asked May 1, 2020
188 views
How many different terms are there in the expansion of $(x_{1} + x_{2} +\dots + x_{m})^{n}$ after all terms with identical sets of exponents are added?