1. Other
  2. Other
  3. this is a 3 part question parts a b and...

Question: this is a 3 part question parts a b and...

Question details

This is a 3 part question. Parts a, b, and c are shown below. Scroll down for b and c.

The goal of this problem is provide a combinatorial proof of the identity: r+n-1 r+n-1 The argument is called a stars and bars argument. (a) We start by creating n - 1 dividers (or Bars). This divides space into n boxes: Box 1 is the space before Bar 1, Box 2 is the space between Bar 1 anod Bar 2, ..., Box n is the space to the right of bar n -1. Now place r objects (or Stars) into the boxes. We can put as many objects in each box as we want. To illustrate this, suppose that n 5 and r-7, then one way to deo this would be where two objects go in Box 1, zero objects go in Box 2, three objects in Box 3, one object in Box 4, and one object in Box 5 For arbitrary n and r, how many ways are there to distribute the r objects in the n boxes? Explain your answer (b) Now, suppose that we are given nr 1 empty positions. We must fill each position subject to the following stipulations In each position we must place either * or . . We must use r s and n - 1 s For arbitrary n and r, how many ways are there to do this? Explain your answer (c) Using parts (a) and (b), conclude the identity holds (Hint: Perhaps show a bijection between these two sets of objects)

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution