In this exercise we will prove Theorem 2 by setting up a

Chapter 9, Problem 49E

(choose chapter or problem)

Problem 49E

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,…,n} and the set of r-combinations of the set T = {1,2,3,…,n + r − 1}.

a) Arrange the elements in an r-combination, with repetition allowed, of S into an increasing sequence x1 ≤ 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 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 {x1, x2,…, xr} of T, with 1 ≤ x1 ≤ 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 − l, r)  r- combinations with repetition allowed from a set with n elements.