Solved: In this exercise we will prove Theorem 2 by

Chapter 5, Problem 5.5.49

(choose chapter or problem)

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 = {I, 2, 3, ... , n} and the set of r-combinations of the set T = {I, 2, 3, . . . , n + r - I }. a) Arrange the elements in an r-combination, with repetition allowed, of S into an increasing sequence XI X2 ... xr Show that the sequence formed by adding k - 1 to the kth term is strictly increasing. Conclude that this sequence is made up of r distinct elements from T. b) Show that the procedure described in (a) defines a one-to-one correspondence between the set of rcombinations, with repetition allowed, of S and the rcombinations of T. [Hint: Show the correspondence can be reversed by associating to the r-combination {xI,x2, . , xr } ofT, with l XI < X2 < ... < xr n + r - 1, the r-combination with repetition allowed from S, formed by subtracting k - 1 from the kth element.] c) Conclude that there are C(n + r - 1, r) r-combinations with repetition allowed from a set with n elements.