Today, I'd like to talk about the bagel problem. Let's suppose that we are going to buy a dozen bagels, 12 bagels, and we go into the store and there are several kinds. There might be plain bagels and poppy bagels and sesame bagels and onion bagels and everything bagels, potato bagels. There might be even blueberry bagels. And the question is, how many ways for a given number of kinds of bagels, can we purchase a bag full of 12 bagels? Let's say that I want to buy a dozen bagels and there are 4 kinds, plain, poppy, sesame and onion. I might buy 3 of each kind, and that would make a dozen. But it's possible that I really like poppy, so I might buy five poppy, and then I would buy fewer of the other kinds. There's every possible combination. For example, I could just buy all onion, and none of the others. I can buy eleven and one, I can buy, you know, eight and one and one and one and one, whatever works out to be 12. So I have total freedom, and if I'm picking and choosing, the order in which I choose things does not matter. It's not like I'm gonna, you know, which bagel am I going to choose first? Doesn't matter. The only thing that matters is the total outcome at the end of the game. You have to buy 12 bagels, and you're not required to buy at least one of any of the kinds. You can really just buy, ignore one of the kinds, or ignore all but one of the kinds. So the store will not run out. They have deep bins. Even if you're buying 4 dozen, or 10 dozen, they will keep supplying you with the bagels you need. How many different combinations of bagels can I get in a bag? Okay, well, I think what we should really do is we should focus on numerical examples, and see what the point is, and then at the end, we'll have some formula. So think about a dozen bagels. Some people might think a baker's dozen is thirteen. But let's say 12 bagels, and we might, to start, vary the numbers of kinds. Like, suppose we go into a store that just sells traditional plain bagels. How many different ways can buy 12 bagels? The answer is just one way. We might go into a slightly more interesting store that has 2 kinds of bagels. Plain bagels and chocolate bagels, and then how many ways can we buy the 12 bagels? So now the answer is more interesting. We can buy 0 plain bagels. We could buy 1 plain bagel. We could buy 2 plain bagels. We can go all the way up to 12 plain bagels. And then of course the other bagels, the bagels that are chocolate, will just fill in, so that all together we get 12. How many ways are there to buy the 12 bagels when there are 2 kinds? And the answer is given by this range of possibilities, and actually there are 13 choices. If I look at all the numbers from 0 to 12 inclusive, 13. When there are 2 kinds, namely, it's the number of bagels you're buying plus 1. That'll be the answer. Now, let's say there are gonna be 3 kinds. Blueberry, let's have bubblegum, Brady: "A bubblegum bagel?" That's gonna be tough. The third bagel will be caramel. And then the number of blueberry bagels that we buy can be anything from 0 up to 12. And then the number of bagels left for the other 2 kinds will go from 12 down to 0. Now, we already saw that if we're buying a dozen bagels and there are 2 kinds, the number of ways of doing that is 13. If I'm buying 11 bagels and there are 2 kinds, the number of ways of doing that is 12. And if I'm buying 0 bagels and there are 2 kinds, the number of ways of doing that is 1. And so the total number of ways of buying these 3 kinds of bagels, when you're buying a dozen bagels, will be the sum of all the numbers from 13 down to 1. And that number is the sum of the first 13 positive integers. And there's a formula. If I have the sum of the first n positive integers, that formula is given by n times n plus 1 over 2. So in particular, here, the n is equal to 13, so the number of ways of buying bagels when there are 3 kinds will be 13 Times 14 divided by 2. If we were thinking about a general formula, we might think of that 13 as 12 plus 1, and the 14 as 12 plus 2. So it's a number like that. It's a fraction that involves a product of two numbers, and then you divide by 2. We could do this forever. So, for example, if there are 4 kinds, then we might say that we have maybe onion, and the onions would go from 0 up to 12. And then whenever we have a number of onions, we would therefore have a number remaining for the other 3 kinds. So, if we have 0 onions there will be 12 remaining for the other three kinds, and if we go all the way up to 12 onions, there will be 0 remaining. And we saw that if there are 12 bagels to be purchased, the number of ways of buying 3 kinds is 13 times 14 divided by 2. And if there are 11 bagels, there should be 12 times 13 divided by 2. And we keep going in this way. If we have 0 bagels, the number is gonna be 1, and at least in this formalism, well, I have to take 0 and add 1 to it, and 0 and add 2 to it, and divide by 2. So that's also gonna be 1. So I'll have a sum of numbers like this. You might think that there would be some way of evaluating that sum, but the answer is not obvious until you try to do some kind of analysis of a formula. And in fact what is really needed here is some other perspective, some other way of doing the problem. Let's say we're doing four kinds. So the first kind that I wrote down was onion, the next kind might be blueberry, the next kind might be bubblegum and the final kind will be caramel. We have our 12 bagels, so I'm just writing 12 stars. So far these bagels are unassigned in terms of their flavor. So so far we have these twelve bagels, and I've just written them with asterisks, known in the trade as stars, and I have to decide which of these stars will be onion, which of the stars will be blueberry, which will be bubblegum and which will be caramel. And the way I will do that is to place dividers between the kinds. So let's say that I want to have only one caramel. So I will put a divider separating off the caramel from the rest of the bagels. And then there's bubblegum. That's a little sketchy. Maybe I'll take two bubblegums, so I'll put a divider here, and then the bubblegum range from the first divider that I'm writing all the way to the right, to the second divider. Let's say I really like blueberry and I'll take four of them. So I'll write the blueberry bagels here. And that leaves 1, 2, 3, 4, 5 bagels for the onion category. So, what have I done? Well, I've written in a line a certain number of symbols. How many symbols? Well, there were 12 symbols for the bagels to start, and then, in order to separate out the 4 kinds, I needed 3 dividers. That's a really key point, that the number of dividers is one less than number of kinds. And all together I've written 15 symbols, and these 15 symbols, 12 are stars, and the remaining symbols are called bars. So what I have are stars and bars. I have summarized my choice of kinds of bagels, onion, blueberry, bubblegum and caramel, by writing down the bars that are interspersed among the stars. And the key point to this whole analysis, is that I can put the stars and the bars in any order I want, and for each order, that gives me a choice of how my bag will be constituted. And in order to figure out where the bars go relative to the stars, what I have to do is I have to contemplate some tableau that is completely blank. It's devoid of symbols. Where all together there are going to be 15 symbols, and every one of these slots is capable of housing a star or a bar. And the rule, when I make my final decision, is that of these 15 slots, 12 of them have to be stars and 3 of them have to be bars. Brady: "So Professor, when you fill out your stars and bars on this, basically if you have 0 of any flavor, it just means you'll have consecutive bars in that list." That's right. Except, for example, suppose I want no onion, right - whatsoever, then I would start with a bar, and to the left of the bar, there is no onion, there's nothing. And then to the right of the bar, there will be 12 slots for bagels and 2 more slots for bars. So what we've done is we've related this bagel problem to another kind of problem. It's a problem where there are 15 slots total, 3 of the slots are bars, and 12 of the slots are stars. And we just have to decide which are which. So this is a standard combinatorial problem. There's a very simple formula involving factorials. So let's say that I want to analyze this problem I want to make the choice. So what I'll do is I'll say there are 15 slots to begin with, and I have to figure out where the bars go. So let's say I'm gonna place my first bar somewhere. There are 15 possibilities for that first bar. So I write the 15 -15 choices. Once I have placed down the first bar, there will be 14 remaining choices for the second bar, so I'll multiply by 14. And then, there will be 13 choices for the third bar, and I seem to have this product as the number of ways of making my choices. However, that's not completely correct, because when I put down these bars, these bars all have equals status. It's not like there's a first bar, a second bar or a third bar, even though we do have an orientation, there's left to right. When I say I'm gonna put down my first bar, I could have put down this bar, this bar or this bar. And so I have to divide by a factor that shows you the number of ways of permuting around the 3 bars. And the number of ways of doing that is there are 3 bars, I get 3 choices to say which one was gonna be the first, and then two choices remaining, to see which will be the second. And then there's only one choice for the third bar. Brady: "So that's removed the problem of ordering." That removes the problem of ordering. And so what we have here for 4 kinds is we have to go back to the previous situation, where we were looking at 1 kind and 2 kinds and 3 kinds, we have 13 which is 12 plus 1, we have 14 which is 12 plus 2, and we have 15 which is 12 plus 3, and then we divide by 1 times 2 times 3. So that's another way to summarize what we have here. And if you are familiar with the notation of combinations or binomial coefficients, this product divided by the denominator product is written 15 choose 3, and 15 choose 3 has a standard notation that identifies what it is. It's the product of all the, the first 15 positive integers, that's called 15 factorial, divided by the product of the first 3 positive integers, that's 3 factorial, and then divided by the factorial of 15 minus 3, that'll be 12 factorial. And in fact, you can see that this is another way of writing what I've already written. Because if I take 15 factorial and divide by 12 factorial, I am taking the product of the first 15 integers and removing the product of the first 12 integers, and what's left are the integers from 13 to 15. 13 times 14 times 15. So 15 factorial divided by 12 factorial is the same product that we have in the numerator, and the 3 factorial is 3 times 2 times 1, which also appears. And what's interesting about this formula is that there's a symmetry. It's symmetric between the number of bars and the number of stars. And that makes perfect sense, because when I'm choosing the bagel kinds, I can say, well I'm gonna choose the places where the bars go down, where the dividers go down, but symmetrically, I can choose the places where the bagels go down, leaving 3 remaining slots for the bars. Brady: "To generalize it, if you had had to buy 20 bagels and there were 6 flavors." Okay, so if there are 20 bagels that means 20 stars, and if there are 6 flavors that means there are 5 bars, and the answer then, would be that I take the total number of slots, which will be 20 plus 5, and I choose symmetrically either the 20 slots that are stars, or the 5 slots that are bars. Yeah, this is the famous Berkeley Campanile. Yeah. [chimes that have been interrupting lesson continue] So let's say, in general, that we have n bagels and there are k kinds of bagels. Well, k kinds corresponds to k minus 1 bars. And so the total number of symbols is going to be n, which is the number of bagels plus k minus 1, which is the number of dividers. And the number of ways of choosing the n bagels when there are k kinds is the number of ways of choosing k minus 1 things from a total of n plus k minus 1 slots. And symmetrically, that's the same as choosing n things from a situation where there are n plus k minus 1 slots. And let me just also write that in terms of factorials, if you like. This is n plus k minus 1 factorial divided by the product of two factorials, n factorial and k minus 1 factorial. Brady: "What happens if we have more flavors than we need bagels? "Like if you are only buying 5 bagels and there are 10 flavors?" It just means that there will be quite a few bars that are either at the end of the configuration or next to other bars. The same problem occurs in disguise if you ask students the following sort of question. Suppose you have a bag of 12 identical lollipops. and there are 4 children, and you want to distribute these 12 lollipops to the 4 children. How many ways can you do that? The answer is that you should take these children, and you should give them temporary names. You should call one child Onion, one child Blueberry, the third child will be called Bubblegum and the fourth child will become Caramel. And so you have really exactly the same problem, and it has exactly the same answer. ...there's only one thing to switch to in this case, it's door number three. Are you gonna stay with your choice or are you gonna make that leap to something different? And very often contestants would stand there agonized, right, so they've got some new information - stick or switch - stick or switch
