Stars and bars

Transcription

In this quick video we are going to look at an important counting problem that is affectionately called the stars and bars problem. Here is the set up. Suppose that we had a collection of colored candies and we want to make a bowl of seven candies. We want to make a bowl of seven candies and we want to know all the different combinations of colors we can put in the new bowl. So here is the idea. The key to understanding this kind of counting is to understand a secret code called the stars and bars code. We will do that in the following way. Since there were three colors we are interested in and that we want to select seven candies. We are going to note that there was some yellow candies and there were some blue candies and there were some red candies. Now we could pick seven yellows and put them in the pile, or we could put seven reds, or seven blues, or some combination of them to add up to a total of seven. So here is the idea. Let's set up a special code that we could tell what combination we have got. Then I'm going to put two bars here and then I'm going to put seven stars. If I put seven stars here then it would mean that I was putting seven yellows no blues and no reds. So let's look at that code. One, two, three, four, five, six, seven, and then a bar and a bar. That would mean we had all yellows. Notice I could give a code for all blues. I would not put any in this first area, then one, two, three, four, five, six, seven, all blues and no reds. Of course the code for all reds would be two bars and one, two, three, four, five, six, seven. And in fact, any combination can be made up with the stars and bars code. For example, we might want to have three yellow, one blue, so now I have used up four so I have got to have three reds. So every combination of seven candies can be expressed as one of these stars and bars codes. Now notice that in each one of these codes there are one, two three, four, five, six, seven stars and two bars. So there is a total of nine slots that we need to fill. In fact to count up all these codes, which would be all the combinations of seven candies we could make, we really need to fill in nine slots. I need to decide where to put the bars and rest will be stars. Out of the nine slots, I need to pick two of them to be bars. Or equivalently, out of nine slots pick seven of them to be bars. You can show these are equal. You could look at a more complicated problem. By more complicated, I mean with larger numbers. Eight different colors and we want to pick twelve different candies. How many ways could this be done. Well, to get the eight different colors, I would need seven bars. Do you see why? Up here, remember, when we had three colors we needed two bars. We are going to need twelve stars. There is going to be nineteen different slots and you need to pick 7 of them to be bars. Or of the nineteen different slots, you need to pick twelve of them to be stars. Ok, that is the end of the video.