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.
Unfortunately, we don't have that question answered yet. But you can get it answered in just 5 hours by Logging in or Becoming a subscriber.
Becoming a subscriber
Or look for another answer