Hi, everyone. Let's get started. So our topic today is combinatorics counting. So while waiting for others, we can start with this warm-up question. In how many different ways can we choose one white and one black square from the checkerboard so that they are not in the same row and not in the same column? And the checkerboard, as you can see, that is a standard one, 8 by 8. Oh, 16 by 16, right? No, 8 by 8. Yes, 64 squares. And we have to make sure that we need to choose one white, one black, and they are not in the same row and not in the same column. You can choose one color for one square first and see based on the choice what can we choose for the second one. So if I choose, suppose I choose, you can choose a white or black, like here. Suppose I choose a black square, then, so it's a checkerboard, right, so we have 32 blacks and 32 whites, right, half-half. So if I choose black, right, I choose, like, there are 32 ways to choose a black square. And once I've chosen this black square, for example, the 32 choice, once I choose this one, can I choose any of the 32 whites, or there will be some restriction which square I'm not allowed to choose, right, so that would guide our next step, because we are restricted by the fact that the two squares cannot be in the same row and not in the same column, so that means just think for a moment which square I'm not allowed to choose. And then you can find out how many ways we can choose the white square. So I choose it over here, so that means everything in this row I'm not allowed to choose, right, and everything in this column I'm not allowed to choose, right, and in each row there are four white squares, and each column there are another four white squares, so in total there are eight white squares that I'm not allowed to choose, right, so that means there are only 32 minus 8, which is 24 white squares that we can choose after we've chosen that one, so the total would be 32 times 24, right, 32 is 2 to the 5th, 24 is 2 to the 3rd times 3, so it's going to be 2 to the 8 times 3, so that would be, I think, 2, 1, 2, 5, 6, right, 2, 5, 6 times 3, yes, so that's 7, yeah, times 3, which is 7, 6, 8, at the end of our answer, 7, 6, 8. So that's what we are doing today, counting different ways, you know, we can, yeah, things like that, we can take out two squares of different colours, counting different ways we can arrange n items. So the two, that would be the sort of lesson plan for today. First we will talk about two fundamental problems in counting, permutations and combinations, and then we move on to counting techniques, and at the end we do a little bit with probability. So basically you've seen this before, right, permutation is when you order, we arrange things when order matters, and it's very different from combination when the order doesn't matter. So for example, if I have three objects, A, B, C, if I permutate them, there are six different ways I can permutate them, six different ways I can put them in a row because the order matters, A, B, C is different from A, C, B is different from B, A, C, B, C, A, C, A, B, and C, B, A, while if I do a combination of them, then A, B, C, the order doesn't matter, so I just have only one way of doing it. Yeah, so that would be the distinction between the two. So let's go a little bit deeper into permutation. If we have n objects, we want to put them in a row, then we know that there are n factorial ways of doing so, right, because the first object, we have n different ways to do that, the second, and so on and so forth, so that's the most fundamental formula, n different ways to permutate an object, the three objects earlier and that three factorial is six different ways. So now if I want to find the number of permutations of size r from a group of n, so for example, in a group of n students, I want to choose three of them. For example, the first one is going to do math kangaroo, the second one is going to do math cow, and the third one would do AMC, right? So for the first student, I have n different ways of choosing the first one, and then after the first one has been chosen, then I have n minus one ways of choosing the second student, and then n minus two ways of choosing the third student, and then this would be, I think, the most intuitive way to find the number of permutations of size n from a group of n students. So just multiply n, n minus one, n minus two, all the way to n minus r plus one, and for that, this is a compact formula, n factorial divided by n minus r factorial, but most of the time, you can just do it by choosing one at a time. And then there's one thing that we see a lot, that's the permutation with repeated elements. So for example, I have these letters A, B, C, D, E, right? So if I have, suppose, one, two, three, four, five, seven letters, if they are different, like E, F, G, then I would have a seven factorial ways of permuting seven letters, right? But because the letter E appears three times, so I actually have to divide by the number of ways, this is repeated, so I have to divide by n factorial, three factorial ways that take into account the fact that the last three letters are the same. And this formula is very intuitive. If you have like E, E, E, and then you would have, for example, F, F, then it would be like nine factorial, and then we divide it by three factorial to account for the fact that we have the three identical E's, and then we divide it by two factorial to account for the fact that we have two F, right? So I think for that, that would be clear. So repeated elements for permutations. But because now the order doesn't matter for these k objects, then I have to further divide by k factorial. So this is very much related to permutation except for this k factorial here. And for example, if I have a group of 20 students, 20 kids, if I need to take out three kids for three different roles in a movie, in a play, for example, then the first one has 20 ways of, have 20 ways to choose the first student, have 19 ways to choose the second student, and 18 ways to choose the third student, so that is permutation, right? But because the order doesn't matter, I just need three kids to do the cleanup at the end, doesn't matter who's first, who's second, who's third, so I have to further divide it by three factorial, and then we have this compact formula, 20 factorial divided by 17 divided by three factorial. But really, most of the time we want to understand the logic of why we are using that formula rather than just use formula itself. And then this one is also kind of intuitive, right? There are one way to choose 0 or to choose n elements, then the n way to choose 1 or choose n minus 1, and the formula is symmetric in k and n minus k, right? You choose, whether we choose k or we choose n minus k out of n, the formula is the same. Okay, so let's do one problem and hopefully we're going to clear up everything about combination and permutation. How many natural numbers have the sum of their digits equal to 10 if each digit can be either a 1 or a 3? It takes some time to do this, so take some time. We're going to do it in two different ways, one using permutation, one using combination to have a side-by-side comparison between the two. I can just start it by writing n and 10 as sum of ones and three, right? So the simplest one is that I just do this. Okay, so that would be the first case. And now I, maybe I added three. So that's gonna be the second. And then I do a 10. So now I know how to do it. It's just one times four, four ones, and two times two. This is case work where it looks like we just have to do case by case. It takes a lot of time to do each case. You could also send the partial answer. For example, for this one, we know that it's going to be a 10-digit numbers, right? All n's, right? So all 10 digits are ones. Um, so there's only one way, right? So that one, that one is most straightforward, so only one number. Um, so it'd be one number. What about the second one? Now, the second one, we have seven ones and one three, so that's going to be an eight, right? It's going to be eight-digit numbers, right? Each of them have eight digits, and how should we, how can we calculate the number of different numbers in this case? We can also send the partial answer if you have through the chat. So this is a case where we have a kind of sort of standard way of thinking about it. So let me just get started on that standard. You may have different ways to do that, but one way to think about that is that I put like eight placeholders, right? So I have eight placeholders for eight digits, one, two, four, five and eight digits, right? And then I only need to choose one for the digit. I need to choose one for the digit three. And after I've chosen a place for digit three, then the rest, I just fill in with digit one, right? And have actually no choice over the rest of the digits. So actually if I do this, I would have a, see like one place out of eight, right? So that actually is going to be eight choose one. And that is actually eight, I have eight different choices to choose which place I want for number three. Okay, good. We have some answer. Let's see, okay. And then for this case, it's going to be have a four digits one and two digits three, right? So again, I'm repeating the same method. I would have a eight digit number, so I'm sorry, six digit, right? So I choose, I put six places a placeholder. Now for this one, right? We need to choose two positions, right? Two positions, four digits three for digit three. So I had a three, three, but then the order doesn't matter because this is when, I mean, you see the numbers is not big, but it's important to understand between permutation and combination and like small basic problems so that we can use them to solve for like more complex problems like this. So in this case, the thing we realize the order doesn't matter, it doesn't matter. I put the first three here and the second here or vice versa. So in this case, actually it has to be combination, it's going to be how many ways can I choose two places out of three, right? So I put C to six, which is six times five, right? But then I have to divide it by two factorial. Six is the number of ways I can choose the first position for the first digit, five is a position for the second digit, but because they are the same, so I have to divide it by two factorial. So I have a 15 ways of making, I have a 15 six digit numbers, four of them are one and two of them are three. And likewise over here, I have a four positions, right, I have a four positions and I need to choose one for one or three for three doesn't matter, but it's going to be four and three. So that four and three is just four, right? So we add one, we add eight, we add 15 and we add four, and the answer is 28. If I make mistake, Andrew, make sure to correct me, it's easy to make mistake over here. And so for 18, and this is a very sort of standard technique we use when we construct numbers like this, you can use sort of case work method or construction. And then I just want to also mention that we can also think of it as a repeated permutation, right? So in the first case, it's easy, I have a just one, one, one, one, one, one, so I have only one number, right? So one number, so that is straightforward. The second case, now if we can think about it, we actually have a one, one, one, we have a seven, one, right? And then we have a three. So if we think about it, it's actually, we have eight digits, eight factorial, but we actually have to divide by seven factorial because the one, I repeat seven times, so again, we have eight, right? And then for the third case over here, what we have that we have one, one, one, four times, you can think of it this way, instead of thinking like a six placeholder, I think of, I can make a six digit number out of four one digits and two digit three, right? So according to our repeated permutation formula, it's going to be six factorial divided four factorial for ones and two factorial for three. So that again gives me 15 just like this one, 15. And the last one is straightforward, it's four, right? So this is repeated permutation, and it's very much closely as you can see that related to computation, combination. Is that clear for everyone? Yeah, I want to make sure that we're clear on this page because these are, as you know, sort of the most fundamental problems in incombinatories, if we want to get it. Yeah, okay, so I will move on, but we can come back at the end if you have questions. Okay, so talking about counting techniques, we already use a couple of them in the previous questions, right? We use casework because a lot of the time we cannot just like straight away go to the answer, we got to break down our problem into exclusive cases. If somehow the cases are overlapping, then we have to be careful to account for overcounting. Then constructive counting is a lot of time we actually have to construct the solution. In this case, more or less, we were constructing the numbers, right? Sometimes we even have to be more explicit than that, but to construct it. Then complementary counting, this one you see a lot in other types of problem, that sometimes it's hard to count directly than we count indirectly, right? So, for example, if someone asked us to find how many three-digit numbers that are not divisible by 11, so that would be harder to count. Instead, I know that there are 900 three-digit numbers, and I just have to subtract away the ones that are multiples of 11. So ones that multiple 11 are easy to calculate because they form a arithmetic sequence that I can easily count, right? So that is an example of complementary counting. And the thing that gets us most of the time, another thing is recursive counting. It's just like when we count a large case, we can, instead of counting a smaller ones and build up on that. For example, the Fibonacci sequence is a famous example of sort of recursive formula because if we know the previous two numbers, then we can calculate the next one and then we just do work like that. But a lot of the time, the combinatorics questions are complicated because of the constraint or restrictions, which we're going to see. If we don't have any restrictions, we can just straight away apply permutation and combination is a different story. But a lot of the times, we have to deal with restrictions. So let's see this question. So here, a little bit of restriction here. How many 10-digit numbers can be constructed using the numbers 1, 2, and 3 so that any consecutive digit differ exactly by one? So this is it. The restriction, the two, any two consecutive digits has to differ by one, right? So if we have a no restriction, it's going to be much easier because of this. So I think you can do, definitely you want to construct a few numbers. Construct a few numbers. And then, yeah, I think we may need to use space. Well, but let's get started by just construct a few numbers. And then, you know, 10 digits is long, but you can just use fewer digits, right? You almost know, as you can see, it's not always about combination or permutations. There's so many different things. Sometimes we just have to list things out without using any formulas. Here's a diagram if you can, like the drain that sort of branches out the tree diagrams. That may help you if I see the structure. Very good, I started having answers, so it's another way in which, you know, the strategy and the way we represent, you know, our data in a sense, that's important because that allows us to see the structure, right? So suppose that I start with a one, just do a simple case, I start with a one, and then the next digit has to be two, right? There's no other choices. And then I start with a, when I'm at two, I can either go up to one or go down, go up to three or go down to one, right? So I could do like one, and then I could do three, just exploring the branches out like this. And then with one, I can go to two, and then three, actually I also have only one choice, let's go to two, right? So once you see a thing like this, and maybe, maybe I started seeing some pattern over here, and then maybe we're going to, you know, just put them together like this, the two branches going to meet at two again. And at two, I know that, again, this structure repeats, right? Because the next digit has to be one, and the next digit has to be three, right? And that's what we have, we are using really constructive counting, we have to construct our numbers, but we do it in a way so that the pattern is pronounced, you can see clear the pattern. And then how many times I have to do it? We need, how many, yeah, we can just, you know, finish it here, we need two, right? So that's one, one, two, three, four, and then one and three, so in the end I would have to finish with a two, right? And how many numbers do I have in this case? So this one, there's only one, this is going to be two, right? I can just count the number of paths over here, so here I have a two, two choices from two, but over here I have only one, so it's going to be two, two branch out, two branch out, two branch out, so I have two to the fourth, right? Sixteen numbers with this starting from one, right? And that, again, is a case where, because we have only three cases, the first digit is one, and now we can do two, but again, another thing that I should add here is that we also use symmetry, because after we do three, right away we should think about, I'm sorry, after we do one, right away we should think about three, right? Because the three has exactly same structure as one, so it's going to be two, and then one and three, and I repeat exactly the same structure, and we go back to two at this point, at the end point, and then I have another two to the fourth numbers, right? And two is different because it started branch out right away from here, one, two, three, and then it goes back to two, and I would repeat it five times because eventually the last one, remember to count, this is two, right? So the last digit actually branch out to two and one and three instead of converging to two, so I have five times of this is two to the fifth, which is thirty-two, and if we add everything together, it is sixty-four. So this is another sort of typical math kangaroo problem when we do not always have to use a formula, and we just have to list things out and observing the patterns, make an organized list and think that these are terms that you use for lower grade. So I put this one here, it's good if someone gets the correct answer, let's go to the next one. This is also a very nice problem, it's very small numbers but I think it's a kind of creative problem. Veronica has five rings on her fingers as shown in the diagram. She takes them off one at a time, in how many different ways can she do this? So let's make sure that we understand the question, right? So she has two rings here, and then in the ring finger she has three of them, and of course she has to take them according to this order, right? First in, last out, so this one has to go first and this one and this one in that order, and that is counting with restriction. So let's see if we could figure this one out. Very good. Some correct answer. You could, this is one of the questions that you also can try to do it, you know, in different ways if you already got one answer. Maybe try to think about it in a different angle to see, you know, you can come up with different solutions. I just denote it this way so that it's easier for us to refer them to later. X and Y are the ones that we can take out in any order. Y, A, B, C, we really have to take out A before we can take out B and before we can take out Cs. This is also one of the questions you can probably list out everything, but also have to do in a way that you can keep track of it. So, for example, let's see. Yeah, it will be hard, but you know what, sometimes I think there's a merit in listing out a few, you know, a few different items and then that may help you, you know, find the general solution without having to list out all different possibilities, but I think, yeah, there's a merit in doing so in this question. So let's start one way of thinking about it. So just like what we did for the first question in which we need to construct, right? So think about this in a way like I have to construct a five-digit number such that ABC has to be in that order from left to right, right? That's another way to think that. I guess I'm also not good at communitorics, like my favorite subjects of algebra for geometry. For example, everyone has a topic that sort of he or she is more comfortable with, right? And if a subject that we are not comfortable with, we just have to do a lot, a lot more practice than other topics. So for this one, with experience and I sort of thinking maybe I can think a bit the same way that I have a five places and I need to find three places for ABC, right? And then so I need to find two, three places. I need to find three places for ABC. And then after I found three places for ABC, there are two places for x and y, right? And then for x and y, we need to multiply by two factorials because x can be in one and y can be other or y and one and x another. The question is that how many different ways I can find three places for ABC? Is it permutation or is it combination, right? That's when sort of our logic comes into play. The number is not big, but it's important to understand whether it is permutation or it's combination, whether the order matters. And in this case, actually the order doesn't matter because if we have like the place one, two, three, it doesn't matter. You just have to choose three numbers, one, two, five, for example. You just have to need like a one, two, five. And once you chose this place, there's only a unique way to put ABC in. So it's really finding three spots out of five spots. It is a combination problems, even though it looks like could be a little bit confusing with permutation, but actually it's combination. So we're going to have to take c, we have to take c, three, five or five choose three. And that would be, remember it's going to be five times four. You can do five factorial divided by two factorial times three factorial, or you can do five times four divided by two times one, and it's going to be 10. So we have a 10 different ways to choose three place for ABC. And after that two place for x and y, we can do x and y or y and x. So we need to take 10 times two equal to 20. So that's one way to do that. And the second way to do that is that to do this question is that instead of choosing three places for ABC, I follow the same thought. I have a five different places, but now I need to find two place for a and b, for c. I need to find two places for x and y. And this one actually is going to be permutation because I have a five different ways to choose the first place for x. And then I have four different ways of choosing a spot for y, so it's equal to 20. And once I've chosen two spots for x and y, there's only one unique way to put ABC in the other three spots. So another way of doing that is actually 20. So I would say that it's actually a very nice problem, question number 20, not the hardest one, not the hardest one, but it is very nice and there's a clear distinction between permutation and combination in these questions. Okay, so put it here, we can go back at the end of the class if we have questions. Okay, let's go into question number four. How many different ways can we go from the highest point of hypotenuse of the big triangle to the lowest point from here to here if we can only go by the side of the small triangles in the way presented in the figure. So here we need to go from A down to B, right, go down to B. And the allowed path is that either we go straight down or horizontally to the right or along, you know, one of these paths, the diagonal path. Right, we can go this way or this way. Yeah, so it comes in like this, like geometry counting, sometimes we count numbers, sometimes we're constructing and sometimes, which is really count paths. If you, actually it's very nice, you can check it out. Yeah, I wish I had put it here, like and then yeah, it just does these questions. Let me try to the answer actually a pretty big number if you know the the past counts the triangles right um this is triangles that you use a lot in in in mathematics right um so we have a one on both sides the diagonal and then you just add like one and one with two or one one with two and down here one plus two with three two one with three it's just like very simple way but has a tons and tons of application in mathematics and one way it's kind of related to that that if we go from the top here and we will go down according to like diagonal path only not straight not horizontal but diagonal like for example you could go from um here down to here and then go to three and go to six for example then actually each number here is gonna tell you how many different paths we can get to it from from this number on the top right so the six way you can get to six there are four ways you can get to to uh four three ways you can get to three it is kind of very neat um problem counting path and um and when i think of it i think it's very much related to to this kind of questions we also have a four recursive formula in pascal we have a you know the binomial coefficients and everything over here it is it's worthwhile to look up a number of passing pascal's triangles and ever so this question um what should we do so um sort of follow what we have with pascal's triangle what we can do is that we can we can we can label it right number right so at this point there's one way to get to this point right just go straight down so there's one way then i put i put the number of it like one on this note right when over here if i go i can go down or i can go right i can go straight diagonal like this is one path or i can go down and go right so actually i have a two ways to get to this point you see like we are trying to construct something like this yeah from here and then over here just like the pascal you only have a one way to go straight so actually have a one way to get to this point one way to get to this point and one way to get to this point right so now um you know you you get the idea um could you try to finish like what number should go here what should go here what number you should go to every note and actually that's what you need to do to calculate the number of paths we could way we can get to point b so quickly draw this on your draft paper and see if we can figure it out hmm yeah and look up this one i think it's very much related And let me give you another hint, school recursive. Sorry, right? Because in order to get, for example, in order to get to this point here, right? We have to get either to this or this or this, right? So I have two ways to get to this point and then from there I can go to this point. I have one way to get here and then I can go here. I have another way to get here, so one way to get to this point and I get to this point. So that means at this point, we have four different paths to get to it, right? And the way we find it out, that number is that we just sum up all the numbers in this vertex. So that would be four, right? And similarly, to get to this point, then I have to either to get this point first or to get this point, right? And have two different ways to get to this, four different ways to get to this, and that means this one's going to be six. I better go down here to get to this. I need to get to this and this and this and I add up together, it becomes six here. For at this point, going to be four and six and six, so that's 16. This one, six plus 16, so now I get 22 over here. Six and one, when six give us eight at this point, and then six and 16, that's 22 plus eight is 30. 22 plus 16 is 38 plus 30, so that's 68. And 68 plus 22 is 90, the biggest number in the list here. So that is sort of recursive formula, but with geometric counting. And you've probably seen it new, but really if you check out Pascal's triangle number path, you would see that this problem actually pretty standard. Yeah, so at least we learned something new about Pascal's triangle. Okay, sorry, let me just copy this one first before we move on to the next question. Andrew, could you do this question? And then, yeah, we have to be, we because have to have a probability, but I hope you can say, I think this is a very interesting topic. So we have this and we have one question with probability. Okay, so barcode is composed of alternating black and white stripes, and the first and last stripes are always black. Each stripe will be either one or two units wide, and the entire bar has a width of 12. If the barcode is always from left to right, how many barcodes are possible? This is a hard question, but again, you can really relate to what we've done in today's class, break down into smaller cases, and our hope is that because we're doing, you know, repeat this a couple of times, and you're going to be really clear about casework, constructive permutation, and combinations after today's class. So just when I read this question, it's kind of, in the beginning, it's kind of confusing for me. So let me just try to clarify that the bar codes here are the black ones. The width of the white one doesn't matter, right? The black one here is one unit, here is two unit, here's one, one and two. The white one actually does matter. But I think it's just a separation for this one, right? Because they say that the entire bar code has a width of 12. I mean, it matters in the sense that we're not counting one and two, we are really counting the black one, right? No, they also count to the width. So they're just equal strips. Oh, I see, okay. So we just have to make sure that total units, okay, I get what you mean, yeah, this is one and two. Oh, I see, yeah, but yeah, doesn't change the solution, but I get what you mean, yeah. And then the total units is 12. Oh, okay, so it's one thing, it starts with a black and ends, okay, Andrew, yeah. Yeah. Andrew, I think we need to give the student a little bit of a hint and then they can get started but you probably have to give some hints in the beginning. So this question is very similar to the first question we did, number one, with the ones and threes. So we can take a similar approach and we can divide it into cases. So basically we have to sum up the one and two such that the sum is 12, right? And we see like how many ones and how many twos are there. So maybe I can just write out and then you can tell us which ones are. So I did 12 equal to one, that's 12. And then Andrew can, you know, comment which one is possible, which one is not, right? It's a long question, even from here, Andrew. So I've been written 12, could have 12 1s or 10 1s and 1 2, or 6 1s and 3 2s, just like in this case, right? This is all the cases, right? So maybe you can comment which case are possible and which case are not. Not all of them actually possible, right? Yeah, so if we try to write out the sequence with the blacks and whites, we can see that for the first case, it actually doesn't work because we end up with a white at the end. Yeah, so because we have a black, white, black, white, so actually we have a, how many number of strips? It has to be an odd number of strips, right? It has to be an odd number. Yeah. So from here, actually it should be odd numbers, odd number of strips, or in this case, like digits, right? Right. So I will, so that means this one is out, right? Because it's 12, so it's out. This one? It's 10 plus 1, so it's 11, so it's in. So it's good, yeah. So it's 11 digits, so that's good, yeah. This one? It's 10 digits. Yeah, 2 and 2, so it's out, yeah. That's 9. 9 is good, yeah. And that's supposed to be 8, but it's 6, but it's still out. Still out, right? Yeah. Because, oh, so I made a mistake here, it's a 2 times 4, right? Yeah, sorry, okay, no, I have to correct it, 2 times 4. So 4, 2 digits of 2 and 4 digits of 1, okay, so that one is out. And then? And then the second last one's in because it's 7, and the last one's out because it's 6. Okay. So we actually have only three cases, right? So 11 digits, or 7, 9 digits, or 7 digits, so yeah. So again, we came back to our original question, so fourth one, fourth one works, oh, fourth one. Okay, thanks, thanks, thanks for the student who corrected those, yeah, on the test. Okay, good. Do you have any comments to send on the test? So we have three cases, and what is the number for this case, Andrew? That one, we just have to decide where the 2 can be, so it's going to be 11. Yeah, 11 places, right, and then we choose 1, right? Yeah. So actually, it's just 11, okay, so by now, I hope we are clear about the method of doing it, right? We have 11 placeholders, and then we just need to choose one spot for digit 2. Okay, very good. This one? That's 9 choose 3. Yes, it's 9 choose 3, or you can see that 9 choose 3, or 9 choose 6 is the same thing, right? Okay, very good, so this one's going to get 6 factorial, 9 factorial, divided by 6 factorial, divided by 3 factorial, you see it's symmetric in 3 and 6, so it doesn't matter which one is k factorial and n minus k, so that's going to be 9 times 8 times 7, divided by 3 factorial equal to 6, so that's 84, is it? 84, okay, good, 84. And then the last one is 7 choose 5, 7 choose 2. 7 choose 2, or 7 and 5 is the same thing, right? So it's going to be 7 times 6 divided by 2, after a while I just couldn't speed up my calculation, so that's going to be 21, right? Right. So 11, 84, 21 is the only number that's big enough, so that's 132. Oh yeah, it's very impressive, you've got the correct answer. It's 116. Oh, 116, okay, sorry. Okay, got to be careful, all the hard work is gone after we circle the wrong answer. Okay, so 116, yeah, yeah, it's a good question, I still confused between the black and the white, thanks Andrew for clarifying it. Okay, good, so you see, we've seen a couple of questions and I hope just review this, you're going to be clear about the method of, you know, putting, constructing numbers with digits like this. So I hope you can say we have a little bit of probability, but we mainly, at this stage, we mainly to deal with situation in which the outcomes of an event are equally likely. It doesn't have to be that case, but, you know, this is sort of the easiest one, so we are mainly working with, in a situation when outcomes in an event are equally likely, then the probability of success is just equal to the number of successive outcomes divided by the total number of all possible outcomes, right? So for example, if we roll a fair six-sided dice, and then we ask what's probability that when it's rolled, the number of dots on the face that is up is an odd number. So all of these six occur with equal likelihood, right, because the die is fair, and there are three events in which three outcomes that are odds are six outcomes, so it's going to be 3 over 6 divided by 0.5, that's probability. So let's quickly do one, this one, with sort of why we put probability in counting, because a lot of the time it's all about counting. If everything is equally likely, so we still have to count the number of successive outcomes, and then we count the number of all possible outcomes, two outcomes, two counting problems. So let ABCDEFG be the eight vertices of a convex octagon taken in order. Randomly choose a vertex from ABCDEFG8 and draw the line segment connecting it with vertex A. Once more, randomly choose a vertex from the same six vertices, but not draw the line segment connecting it with vertex B. So what is the probability that the octagon is cut into exactly three regions by these two line segments? So I should have to be quick and draw an octagon here. So we have a, it's up with eight, so 4, 5, 6, 7, 8, so it's going to be A, B, C, D, E, Okay, so let's try to do this together. Now I have six points, okay, I have six points, C, D, E, F, G, H, right? So we need to connect these with A and then connect with B, right? So that means we would have like, yeah, I don't connect here because it makes the picture really cluttered, but I have like six segments, right? And over here, connect this with B. So I have another six segments and they are independent, so we have a six times six, we've got 36 cases, right? So that would be the total, it's gonna be very cluttered, but that's what I would imagine, right? So among these cases, we have to quickly count how many cases that the two segments that we draw, we actually divide the octagon into three regions, right? So that's really a counting problem, so take a piece of paper and see if we can do that. So for example, A and H is not a solution because it doesn't divide anything. I can connect A with G, for example, right? And then over here, I would also think that we should list things down. So again, case work, right? Case one is you connect A with G, case two, we do A with F, that has some potential, right? Three, we do A with E, right? In case four, we do A with D because A with C. Oh, okay. Do we have case A with C? No, A with C is no good because if we connect A with C, we cannot do B with anything. Because, yeah, so I just put it here. For example, A with G, then B not going with H, right? So if I do A with C, anything that I connect B and then divide into four regions, not three. Okay, so A, D is good. Okay, good. So let's quickly do case by case. For A and G, which segment is going to work for B? If I connect A and G, then for B, I could do B and G, right? It's really like I could do B and G. That's three. That's good. I could do B and F. At some point, I just do it by hand without having, I mean by eye, without having to draw everything. I could do B, G. I could do B, F, three segments. I could do B, E, and I could do B, D, right? So that's good. I just list it here. I would have B, G, B, F, B, E, and B, D. Okay, good. So that would be the case. And then if I have an A, F, good night, I put it up here. Then I have B, F, B, E, B, D. So B, F, B, E, B, D. Actually, you know, everything has a pattern. We already see some patterns here. If I have A, E, then I would do B, E, and B, D, but not B, C, right? So B, E, and B, D. And then if I have A and D, the only thing that I can do is I connect B and D. So a clear pattern here. So I would have four plus three plus two plus one equal to 10 cases. 10 cases in which I could, the two segments, we divide the octagon into three different regions, and we have 36 cases. So it's going to be 10 over 36. Everything is equally likely. And that would be 5 over 18. That's the answer. 5 over 18, right? So again, this is not the only case when the events are not equally likely, but if it is, then we sort of turn it back into counting problems. Okay, good. So I think we are really over time now. Initially, we were hoping, everyone was thinking we could do an hour and a half, but we have to stop at an hour. And just to recap, so formula really helps us do the calculation faster, but really it's important to understand where it comes from and not just to memorize it, where you understand the logics behind. And it's sometimes, lots of times we do the combinatorial problems and the calculation gets too complex and it's time to sort of maybe look at it at a different angle, especially in the exam, you don't have a lot of time, right? So if something got too complicated, maybe we don't do too many case work, we do something else. And then again, if one counting technique doesn't work, try something else. And a great way, it's just like for me, I would, this is not like a topic that I feel as comfortable as algebra or geometry, for example. So even topics that are not good, and then you have to do a lot more practice. And for counting, I find that just doing the same problem in a different way to make sure that you still get the same answer is actually a great way to study combinatorics. So you can pick, some of you have other problem solving, they have a two volumes of counting and probability, one is introductory, the other are intermediate, there are tons and tons of problems. Combinatorics is a topic that is very popular in competition, so we can find a lot in past year exam, later on it's useful. You don't see it in school because it's not as popular as the algebra, but later on when you do computer science, you do maybe statistical physics, then counting is essential. It's a difficult, but very interesting topics. So I hope we learned something in today's class, and I will stay in here. Next week, we're going to move to logical reasoning, a very sort of special topics for math can gurus, and then we have our last three classes on geometry. I will send out the handout so that you can print ahead of time because we need those for geometry lessons. And for now, Andrew and I will stay in case you have any questions about today's classes.

combinatorics

mathematics

counting

permutations

combinations

probability

recursive counting

Pascal's Triangle

casework

constructive counting

complementary counting