## Stars and Bars (and bagels) – Numberphile

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

easy school maths.

I love this episode.

Hooray for multichoice (came up in my research this summer)!

"What have I done?" I would ask myself the same thing if I bought those bagels.

he makes me think of a mix between stannis and the high sparrow

If you see a video about bagels, it's about topology. BUT IT'S NOTTT

What a coincidence, I'm going to have a probability and statistics test tomorrow.

I love bagels…and math

why is the everything bagel rainbow colored lol

The sound sharpies make kills me.

One of the weakest Numberphile episodes. Even worse than the ones with twitchy Cliff Stoll. Huge step down from the Ribet on Fermat video.

Love the sound of the Berkeley campanile in the background. Ah, memories!

🍩

15:40 the fatest child gets the most

Could you also approach this problem using sums? For example, if there are 4 types of bagels (a,b,c,d) and you can choose 12 bagels, then a +b + c + d = 12, where a,b,c,d must be between 0 and 12.

what person doesn't get a baker's dozen ?

Stars and bars is an unfortunate metaphor, as it also refers to the Confederate States of America. Too many Americans (including myself) this is a symbol of oppression, which actually made it difficult for me to concentrate on the content of the video! I would have to hope that if William Feller were explaining this in 2016 instead of 1950, he would have chosen a different metaphor.

Why anyone would buy a plain bagel is beyond me.

A BAKER'S DOZEN !!!!

If three people are on a court playing Chinese Handball per game, you will have two combinations.A,B,C AND A,C,B. Four people will give you ABC ABD ACB ADB BCD BDC ACD ADC Is there a formula to figure out how many combinations I can have every time I add another person? Only three people can play per game.

As an American, every time he said "stars and bars" all I could think of was the Civil War. <sarcasm> Are you a Confederate sympathizer!?! </sarcasm>

I learned this in highschool. Why not just n!/(n-r)!r!?

I was hoping it would be a "factorial" drinking game…

SpoilersIt took him awhile to even say it once.so it's like x1 + x2 + x3 + … + x7 = 12, pretty easy, you just have to take a function which would be (1 + z + z^2 + z^3 + … + z^12)^7 and look for a*z^12 in its extended form, this a will be our result, number of combinations, right?

When you watch a Numberphile video, and kinda understand whats going on

anyone wanna solve this for me?

x is the angle you're facing north/south

if x is 1, you're facing north, if x is -1 you're facing south

if x is 0, you're right in between

y is the angle you're facing east/west

if y is 1, you're facing east, if y is -1 you're facing west

f y is 0, you're right in between, if x is 0.25 and y is -0.5, which angle in degrees are you facing?

13:53 nice little interruption 🙂

In America, we call them doughnuts. Though blueberry, onion, (not bubblegum), cheese kinds are still considered as bagels. Where you call a chocolate bagel or a caramel bagel, we call those chocolate and caramel doughnuts because we consider sweet bagels to be doughnuts. Also, American doughnuts are softer compared to bagels which are hard and are sometimes put in a toaster.

n!/(k!*(n-k)!)

So am I right in thinking this formula works for lottery numbers as well?

Is this video just a calculus lesson? Because I swear I was at a calculus lesson once that thought this exact thing.

I can hear the campinili in the background

phenomenal combinatorics video

What comes every day, but is never there?

Can you guys do a video explaining the drunken sailor problem?

Bagels are made from foam rubber.

As this video was being filmed, Carlo Séquin felt a disturbance in the Force, but knew not why.

I want bagels now… 😥

In Philadelphia we say "begels" not "baygels". Makes watching this video painful.

15:28

There are two ways to do it!Giving one child more lollipops than another one is unfair, so the two options are:

1) Give each child 3 lollipops.

2) The lollipops will remain uneaten.

first Klein bottle guy now bagel guy

The way i remember n(n+1)/2 is as:

1/2 (n^2 +n) which is the same as 1/2 (n+n^2)

which can be rephrased as "the average of a number and its square."

Why doesn't he just say Donuts?!?

Noooooo!

not that many Onion bagels 🙁

they make my mouth taste funny :((

Aren't these donuts….

Ken Ribet is one of the many contributors to the proof of Fermat's Last Theorem.

This is usually referred to as the "Pirates and Gold" problem, at least in the USA…hooray for combinatorics on Numberphile though 😉

What about if there is more choice than the number of bagels we want to take? let's say 12 choices but only 8 bagels to take.

Please help me with a further constraint on this problem.

The constraint is that you cannot have equal number of bagels of any two or more types. (You cannot even have zero bagels of more than one type)

Is there a formula fir this?

Am I the only one who misheard him say 'slots' as 'sluts'? 😐

If you want 12 bagels. And there are 4 different bagels to choose from. Why is it not 4^12?

Hope Bagels

If there are 12 bagels and 4 different kinds and you want to find the number of possible permutations couldn't you just do 12P4 which is 12! / 8! ?

Holy cow Brady helps with lots of you tubers

BackstageScience

Bibledex

BradyStuff

Computerphile

Deep Sky Videos

FavScientist

Foodskey

Hello Internet

Nottingham Science

Numberphile

Numberphile2

Objectivity

Periodic Videos

PhilosophyFile

PsyFile

Sixty Symbols

What's the point?

Words of the World

This video will help me so much in everyday life tbh.

Stars and bars can refer to the flag of the confederate states of America which is often used as a symbol of hate. Just a heads up; thanks for another great video!

Might as well have been Stars and Stripes, eh?

really nice way to explain problems on combinatorics..

Am I the only one who heard "Sluts" instead of "Slots"?

Me watching the video: "Huh, this guy's kind of entertaining, whoever he is."

Me reading the description: "Wait bagel guy is Ken Ribet?? damn, I know that guy, he helped prove Fermat's Last Theorem! "

Was waiting for that formula at the end. Plunk in X choices and Y selections, get Z answer.

Is Professor Ribet still at the University of California, Berkeley?

Can someone point me to a video that uses s&b to solve the following: Using only ODD integers, how many ways (combinations) can you produce a sum of 18?

I remember we studied this in the high school math class.

has anybody ever bought a dozen bagels (and chocolate covered bagels whaaaat)? i'm just going to pretend these are donuts.

I like that the potato and onion bagels just have a big whole potato and onion sitting on top. And the poppy seed bagel has poppy flowers.

Listening to this while I'm at Berkeley studying for a probability course, and I hear 13:30 (the bells tolling). Immediately looked the professor up and yup he's in Berkeley xD

Edit: He showed the Campanile ahhhhhhhhhhh

Onion bagel? That sounds disgusting.

Same solution for number of independent configurations of an object with k symmetric parameters which takes on n values. For example # of independent components of a tensor in R^n with k symmetric indices. :^)

crystal clear!! helped me a lot. Thank you!

is the answer 455 for the last problem?

who else studying for combinatorics test ?

The title of this video: police in Southern US 1861-5

man who eats onion bagels!

The perspective change on this is awesome.

This isn't just crossing the line twice: the line has been re-purposed as a balance beam.

I wonder if he knows that the "Stars and Bars" is a nickname for the Confederate flag.

Really good explanation and animation!! More combinatorics, please!

Thank a lot : )

carbohydrates click-bait

Awesome video! Helpful in my statistical mechanics class 🙂 I also loved it when the Campanile starting chiming, because I was all looking out the window like, "Why is it going off at 4:35?"

i like the part he said 'bagel'

Is it just me or does Ken Ribet look like Inspector Lunge from Monster?

Love it….

Came back to this two years later when I am finally taking combinatorics! Very helpful for studying now that I can understand it better!!

Tim Hortons wants to know your locationThis is as brilliant explanation of stars and bar.

Push the Whopper button!

I started doing the problem myself and decided to mess around, and somehow found myself relating the bagel problem to Pascal's Triangle. I'm going to try and work out how I got there, but allow me to say I'm terrible at explanations and painfully amateur sooooo

Around when he got to 4 bagel types, I decided to try to solve the problem myself. I called the four bagel types A, B, C, and D, and set up 13 sets of bagels; 1 where there are 12/12 D bagels, another with 11/12 D bagels, another with 10/12 D bagles, et cetera. Immediately I knew the last set would have 91 possibilities as it was the same as the answer to when you want a dozen of 3 bagel types. I then went back to when D bagels took up the entire dozen, and said there was 1 possibility. Then I moved onto when I had one empty slot for bagels, and said there were 3 possibilities, 1 for each type of bagel I could put in. I then moved onto when there were 2 empty bagel slots, worked out there were 6 possibilities, and then i noticed a pattern in the numbers. 1, 3, and 6 seemed like a pattern; 1+2=3, 3+3=6. I then decided to take a stab at what the next combination would be (my guess was 10), and lo and behold, the next amount of possibilities was in fact 10. From there, I guessed the rest of them according to what I observed before (10, 15, 21, 28), and realized that I was looking at the triangle numbers. I then added up the sequence, and found out that the method I had just used to find the answer did result in the correct answer: there were 445 possibilities for picking 4 types of bagels.

Just before watching this video, I was watching a video on Pascal's Triangle, and swore I saw the triangle numbers in there. I decided to draw up Pascal's triangle and found the triangle numbers along the diagonal, and above that diagonal, there was the sequence of 1, 2, 3, 4, 5, 6, et cetera. Upon looking at it, I realized that was what I was adding by to generate the triangle numbers was the diagonal above the diagonal of triangle numbers. I then decided to look if the same pattern happened with 3 types of bagels. I found that what I had believed held true; the possibilities in order from 1 type of bagel taking up the whole dozen to the 1 type of bagel not being present at all lead to the sequence of numbers: 1, 2, 3, 4, 5, …, which were all 1 apart away from each other (+1, +1, …). The +1s were all the same, just like the diagonal above the 1, 2, 3, 4, 5 diagonal on Pascal's Triangle. Upon adding up the numbers 1 through 13, the sum was 91, the same as the total number of possibilities for 3 bagel types in 1 dozen.

I haven't managed to prove that the bagel problem's relation to Pascal's Triangle holds true for every iteration, but I have found a correlation no doubt and conjecture that the process I used to find the possibilities for the amount of bagels would still work no matter how many types you had.

The best part of the clicking the Nunberphile video is to watch and read the wild comments.

i still don't understand…..

Bubble gum? Caramel? Those aren't bagels, those are donuts!

9:32 the bars indicate that there should be 10 onion and 2 blueberry, but the onion category is a mix of 5 omion, 1 blueberry, 1 gum and 3 caramel while the blueberry category is 2 caramel.

Finally I understand the idea behind "blank choose blank"! Thank you!

Does he deliberately call donuts "bagels"?

Was anyone else unclear as to why the method at 2:56 worked for three different types of bagels..I don't think most people including mathematicians would have done it that way..because it looks like you're not taking into account all possibilites for all three types..like the three cases where you get only twelve of the same kind. I wouldve done type 1 with type 2 for 13 then type 1 with 3 and then type 2 with 3..that's 13 Times 3 equals 39 combinations then fill in the rest…

Some of this guy's examples of bagel flavors seems more appropriate for donuts to me.

I feel bad for the kid getting onion lollipops.

I am definitely going to use this when I tutor discrete math next semester. This is such an amazing explanation!

Nice to know that Onion from Steven Universe made it into a numberphile video

This video would have been a lot better if he talked about donuts instead of bagels :/