The number of ways to choose k elements from a set of n elements is given by the binomial coefficient n choose k, calculated as n!/(k!(n-k)!). This coefficient can be arranged in Pascal's triangle, where each entry equals the sum of the two entries above it, following the recurrence relation n+1 choose k = n choose k-1 + n choose k. The binomial theorem states that (x+y)^n = Σ(n choose k) * x^(n-k) * y^k for k from 0 to n, and the sum of all binomial coefficients for a given n equals 2^n.
安装我们的扩展，即时搜索任意视频内容
Working Through 009: Book of Proof (en route to The Art Of Computer Programming)本站添加:
We are going to be counting some more today and we've got a bit of a new setup.
Uh this one is it's a kind of teleustrator.
Been working on it.
This is just this this just for the VOD.
Nobody's nobody's tuned in yet.
But uh you can see I've got a little dot here can draw things with. Of course, it's uh it's perfect freehand. Thank you, Steve.
I've messed up all the settings to make them horrible, but I can, you know, I can do all kinds of stuff now. I have complete control.
But today, today we'll be today we're going to be counting. So, we're going to be counting counting some more. Uh we'll see how far we get. uh if I'm very good, we will get through all of this section and then we will finally be proving things.
Maybe we'll get there today.
Okay. Counting subsets section 3.5.
The previous section dealt with counting lists made by selecting k entries from a set of n elements. We now turn to a related question. How many subsets can be made by selecting K elements from a set with N elements?
Okay, K ele what's this? K elements from a set with N elements. How many subsets can be Okay, this is different selecting K entries from elements. And now it's okay. How many subsets can be made by selecting K elements from a set with N elements?
Okay, seems pretty closely related.
To see the difference between these two problems, take A being this set here and consider the non-repetitive lists made from selecting two elements from A.
Fact 3.4 says that there are 3.4 that must be the uh what's fact 3.4?
for O K permutation which we also denote as as P. Hello lovely talent. Sorry. Hello. Hello lovely Terran.
Good username. I am I am learning That's what I'm doing. I'm learning to count.
I'm learning some high level well medium level counting.
Okay, we got a P there kind of. It is math.
It is indeed math.
We're on the way to reading and any percenting the uh the whole of um Donald Kuth's the art of computer programming.
And this is a prerequisite. Well, for me it's prerequisite because I don't know proving things and uh this is called book of proof. So I'm learning to prove things.
Okay.
So so P this thing is uh what is this again? I've just forgotten.
It's this. It's a k permutation which is a k permutation of an element set is a non-repetitive length k list made from elements of the set.
So it's like it's a an arrangement of k's arrangement of k of the sets elements in a row. So we care about order there as well because it's permutation I guess.
Game development and coding gives me good feelings always but too lazy. What kind of feelings does it give you?
Okay.
Consider the non-repetitive lists made from selecting two elements from A. Yep.
Fine. these lists, but there are only 10 two elements subsets of A.
Oh, because of the repetition basically.
Yeah, we get AB here and then we've got well, we should have a BA somewhere here.
So, we've got A and B A BA, but we've only got one here.
Hence, there being 10 versus 20.
Okay.
The reason there are more lists than subsets is that changing the order of the entries of a set produces a different list. But changing the order of the elements of a set does not change the set. Using elements A, B, in A we can make two lists maybe in BA but only one subset. Make sense? This section is concerned with counting subsets not lists. As noted above, the basic question is this. How many subsets can be made by choosing k elements from an n element list?
So this seems like it must be similar to um filtering the power set based on the length of the the length of the uh the set. So I think in builder notation uh this is one I struggle with. Okay.
Two. No, that's the other one. S two. Okay.
So this is let's say X in the fancy P. See if I can draw a fancy P in the power set of let's say X. This is terrible notation.
uh where um the cardality of x uh is equal to let's say two right and then it's uh this symbol. Hello bubbledon. Oh, you woke up from a big old nap. How how big was the nap? How how how discombobulated are you feeling? I always feel very dazed after napping. But maybe you don't.
Okay. So I think that's equivalent to what we've learned before.
But here we're we're counting here.
We're concerned with like I guess the cardality of this set, right?
That's what that's what our question is here. Not just listing the sets out, but counting the number of sets in the power set where the cardality is two. I think happy Nora strayed in with the criticism of the fancy P. I'm sorry.
Uh yeah. Okay. All right. The P is not fancy now. Let me try to draw another one.
No, that's even worse. That's That's terrible. Okay. Bubbledon's saying this notation is a little inaccurate. It should be x in px before the colon.
Yeah, my notation is uh my notation is I thought the colon was like in.
I thought the colon I don't think I've seen in in the uh in the notation I've been learning. Anyway, maybe I'm sure there's different notations.
Um, you have been discombobulated.
You've been so tired this week because of the temperature. Oh, yeah.
Yeah. I've also been uh affected by the temperature in Western Europe. I'm being affected by the temperature in Western Europe right now, in fact.
Very sad.
Oh, yeah. It's the element symbol. Oh, yeah. It's Oh, yeah. I get you. See if I can remember how to erase things. Okay.
Yeah, it's uh It's this right.
It's that symbol.
That's the one I mean. And then it's the colon. Yeah, you're right.
Wow. Obviously, you're right. But now I now I see how you're right. Okay, great.
That's right.
I wanted to get into the comma again.
Obviously.
Oh, I've done it the wrong way around.
Oh no. Oh no. I was sure. I was sure that time because I was like, well, this looks kind of like an E, so it can't be that. But it is obviously because it my memory works in in horrendous ways. Terrible.
Yeah. Okay. Thank you everyone.
It's uh it's it's it's very it's very similar to being being tutoed, but tutored by like eight different tutors at once.
Oh yeah, true.
Yeah, happy Nor, you're right. Subset of that's true. Yeah, that because I guess the subset of constructs that constructs the power set, right? Hello in a climb bottle. Greetings to you too.
Um, can we get a temperature check? What temperature is it where you are?
um without doxing yourself in case you're a very in if you're in a very specific location where the temperature is very unusual. Maybe round it maybe add add or subtract a random number within the range of 1 and zero.
Okay, temperature here is 27°.
I want to know what the temperature is where you are.
The element of symbol was thought of by Jeppi Po of Po. I never pronounced that out loud before. Poythmmetic, right? I suppose at the end of the 19th century to represent the Latin verb est.
So it's a little epsilon. Huh. There you go.
There you go.
All right. I'm I'm I'm back in I'm going back to the I'm back in the book. If you have if you have challenging questions for me, please retain them. I will I will engage with them. I will engage with them later. Um okay. Where where are we at?
Yes. So basically the thing I was thinking was this is this this whole question about counting that we're on kind of feels similar to the power set like we have he hasn't mentioned the power set yet so maybe it's different but okay this section is concerned with counting subsets not lists as noted above how many subsets can be made by choosing k elements from an ele n an element set. Oh, and I missed someone's uh message actually.
Now I think of it. There was something I meant to reply to. Tali, I've been following the YouTube VODs.
Welcome to the Welcome to the live experience.
Um, thanks for following along.
Okay. How many subs yet? Great. Okay.
Definition 3.2. If n and k are integers, then yeah. Okay. I've I've seen this notation before.
It's this these big brackets n and k.
Yeah, I did this did this at school.
Denotes the number of subsets that can be made by choosing oh it's choose it's choose k elements from an n element set. We would read n k is n choose k.
Some textbooks write C N K. I've I've seen I think at school I was taught N big C K.
They taught me that instead of this. Well, anyway.
Pano. Pano. Okay. Piano. Piano. Piano.
Got it. Okay.
Usually the N is superscript, huh?
Well, and a climb bottle is 29 where you are.
That sounds diabolical. It got up to like 32 here earlier this week.
It's not streaming weather, I'll tell you that.
Yeah. Will I survive long? I hope so.
Have a fan which will hope not interfere with the microphone too much. I am UK based.
Yeah, I lived in London for for some time and then I got priced out, but I'm still in the UK. Sticking it out. Um, this is illustrated in the following table that talls the K element subsets of the Oh, no. See, I got to I got to erase some stuff now.
Um, tallies the k element subsets of the four element set a b c d. We're familiar with that set with various values of k.
Okay, there's minus minus one. Okay, great. We're starting off strong minus one.
4 choose minus one is zero.
I guess this will become important later if we start doing induction, right?
Maybe I don't know choose K choose zero is the empty set. I guess these are going to be true whatever the set is. K choose one is going to be just make sure my microphone is not doing anything weird.
Okay. Don't think it is.
Uh K choose two. Yeah. K choose three. K choose four. K choose five is empty.
Okay. That makes sense. Intuitive.
Yeah. Long long enough to get through these books hopefully. Yeah.
Um hello Namir. Hello. Welcome back.
Um Boddon, is this your own whiteboard now? It is. It is.
I uh I I've been playing around with I've been I've been building my own building my own again. My friend called me. Um my friend used to work for TL Draw and I said, "You know what? I've been building my own whiteboard."
And she was just like, "Oh." She just sighed. Horrendous. Worst habit building your own. But cool thing about it is it's got transparency, so you can put it on top of anything, including me. Put it just draw all over all over here.
Um, and it does use uh Steve's Steve of TL Draws perfect freehand, but I've I've I've mutilated it so that it it simplifies the paths a bit because makes my handwriting slightly better.
Um, yeah. Yeah. Yeah. If I had a if I had the technology to to um make the lines thicker at this point, that would be better.
Okay.
All right. So, we got um we got we got some subsets. Fine. the values that appear in maybe there's no he's not mentioning the power set because he's not assuming people have been through that section the values of K appear in the far left column of the table okay fine fine we'll go back up okay that's not very helpful yeah it sounds pretty straightforward um to the right of each k all the sub yeah we get how the diagram works Richard um yeah okay okay uh when k is equal to zero there's only one subset of a that has cardality k namely the empty set.
Fine. Notice that if K is negative or greater than the cardality of of A, then these rain noises back up.
Uh uh greater than. Yeah. And A has no subsets of cardality K. So that's zero.
Okay, in general uh n choose k is zero whenever k is less than zero or k is greater than n. In particular, this means n choose k is zero if n is negative.
Makes sense.
The Soviet notation for this says name is uh C K N. Right.
Cool.
Thanks for sharing that. That's cool. I like that.
Alpha Victor Charlie says there's a decent amount of lag between video and audio. The audio lags behind the video.
Unfortunate.
Okay. Wet says no audio desync.
Less than half a second says bubbledon.
Okay.
How's the temperature of my laptop doing? 71°.
That seems okay.
Hopefully it reyncs soon.
I have no I have no uh I have no debugging tools to get rid of that.
Now you should know how how bad the the desync is. Everyone should know at that point. Um okay.
Yeah, makes sense. Negative negative negative K.
Although it was not hard to work out the values of four choose K by writing our substance in the above table. The method of actually listing sets would not be practical for computing when N and K are large. We need a formula to find one. We will now carefully work out the value of 5 choose 3 in a way that highlights a pattern that belong that points the way to a formula for n choose k.
It's better now. Thank you. Let me know if it gets worse again.
And I'll try and uh I'll try and move my lips uh a half second later than I than I talk.
That would be interesting. It would be an interesting challenge to begin. Note that 5 choose three is a number of three element subsets of this. These are listed in the top row of the table below. Okay, let's look at this table where we see 5 choose 3 equals 10.
Okay, that's this part. I suppose the column under each each subset tallies the three factorial equals six permutations of that subset. Okay, that's the permutations.
The first subset has Yeah. Yeah. Yeah.
Okay.
Yeah, the ventriloquy. Ventriloquy. I don't think I've ever said that word before.
Ventriloquy.
Ventriloquy. Try saying it.
Try saying it uh with a slight delay on your on your audio. Um, yeah. I I sometimes if you're if you're traveling through the UK, do you get this in other countries as well? You you see in the windows um cardboard cutouts of of usually memes, meme people.
Imagine being a meme person, a terrible fate. or or celebrities. Maybe I'll get one so that people can put me in their window.
I don't think that would be a good idea at all, but it will be funny.
Okay. Body of this table has Okay, fine.
Yeah, we get the idea.
Notice that the table consists of every three permutation.
Fact 3.4 forces that there are.
And what is this called again?
Always forgetting fact 3.4.
Gosh, that's annoying.
Fact 3.4. K permutations. I should know.
I should know. I should know that.
Remember, it's K permutations.
K because I'm K and P because it's a P.
So it's just permutations. That's how you remember that.
Yeah. Okay.
There are uh yeah this this is K permutations equals 5 factorial over 5 minus 3 such that such three permutations. Okay great. Thus the total number of lists on the table can be written as either 3 factorial 5 choose 3 or 5 factorial over 5 minus 3.
Okay, he's doing something. I don't know where he's going. Where is he going with this?
He's just saying this is interesting so far. He might might name it at some point.
Working this out, you'll find wait okay which is to say 3 factorial 5 choose 3 is okay fine. Dividing by both sides by three factorial yields 5 choose 3 equals 5 factorial over 3 factorial * 5 - 3 factorial.
Fine.
dividing both sides by three factorial.
Oh, right. So, he just wants to get rid of this so that he can have a formula for for this. Okay, that's where he's going. He's trying to get a formula for n choose k. Fine. Okay.
Okay, fine. Fine. But there was nothing special about the values five and three.
Whoa. We could do the above analysis for n choose k. I should be less bratty towards Richard. He's just trying to help me understand. Um n we could do the above analysis for n choose k. Instead of 5 choose three, the table would have n choose k columns and k factorial rows.
Okay, fine.
Yeah, it's a fact. He's established a fact.
Great. It's this fact. This is the fact established.
If k is between 0 and n inclusive, then n choose k is equal to this formula.
Otherwise, it's zero.
Let's now use our new knowledge to work some exercises. Great.
Badon, you're full of new words today.
Obstreus.
Obstropurus.
Is that a real word? Obviously, it's a real word.
Uh, okay. What does my computer say about what that word means?
Noisy and difficult to control, I suppose.
Yeah, I feel like this I'm I'm going I'm regressing to school school attitude now.
Yeah, I know.
Um, okay. Where are we?
How many size subsets does this have?
Fine.
So, so let me now I've got the formula off my screen.
Get rid of all this.
Let me see if I can remember it.
Whoa. Okay.
N choose K is equal to forgotten it already. N because N is all the permutations, right?
And then it's I think is it this been doing this a lot lately with the um the quadratic formula as a way to test this software.
But this will be my new one. Now that doesn't look right at all. Let me find out.
No, almost though.
Almost.
This end is wrong and then it's right.
Pabloon's commenting on uh you've managed to make it so you now have to erase the whiteboard as well. That is in that was indeed my my objective.
Um my my my model for this software is is the class whiteboard, you know, like a like a lecture theater whiteboard.
I've tried to make it as much like that as possible within the constraints of software. Um and the erasing is is kind of part of it. There is a reset tool, but um and I don't I'm not still not 100% happy with how erasing works, but there are some trade-offs there.
Hence the chalk colors also.
Okay, these are these I sampled from a real chalk.
Well, there's a pretty similar so many bugs.
Something like that.
I should make it so the pen runs out.
No, I should make it like it very slowly fades away like a like a whiteboard pen.
That would be that that would be like my my school experience where the teacher just comes in and none of the all the pens are like invisible but they they persist anyway and then and then they you know it was that was so good. They should do a meme about this. The feeling when like the teacher picks up a like the pen stops working like for the eighth time and they pick up a new pen and it's just like it's so perfect. It's like bold.
It's It's a perfect color. It's just so That That was a satisfying moment for me anyway. Um Okay.
Yeah, we got that.
We got this. Okay. On the Okay, we got Okay. Let me try and inject a few things about this in my mind. So, we've got all What color am I on?
Okay, we've got all of the permutations on the top here.
So there's only one term and it's all the permutations.
But then we cut down the number of permutations by this uh term.
And this term is I think this part does the job of dividing out all of the um all of the all of the permutations that are um not that that are larger than the right size. So if we were going for like n choose like if we're going for like 8 choose three n minus k divides out all of the ones that would be of length four 5 6 7 and 8. So that's that's what this one's doing. And so this one this one feels like intuitive to me. In which case I guess this term here must be doing the job of um dividing out all of the different arrangements of three elements which makes sense because we know that k factorial will be all of the arrangements of k elements all the permutations of of of k elements. So we're dividing out that as well.
So we would never have K on the top here because it's just not not relevant, not important.
We can use different colors.
At some point I'm going to make this more interactive as well. So uh you will be able in some way to draw on this board. But but in a very in a very con in a very constrained way obviously not that I don't trust any of you here but okay that reasoning is exactly right okay brilliant thank you I always thought it was kind of crazy that this division always yields an integer. Yeah, I guess it kind of I guess it is.
Cool. Somebody should prove that.
Probably they have. Um, all right. So, we got uh we got this another example. Is there anything funny about this example? I don't think so.
Just going to skip through that for time. Somebody's using somebody's got some cards here. That's very exciting.
A single five card hand is delta for standard 52 card deck. How many different five card hands are possible?
So in that case we're looking at 52 52 choose five, right? Which is indeed what what is being done. And then that's that's just calculated, right?
That's fine.
This problem concerns five card hands that can be dealt of a 52 card deck. How many hands are there in which two of the cards are clubs and three are hearts?
This seems more more challenging.
Let's give this one a go. Let's see if we can learn anything about this.
Okay.
How many cards are there in which two of the cards are clubs and three are hearts? How are we going to how are we going to work that out?
what comes to me immediately has nothing to do with choosing at all. So, let's I'll just follow my intuition and see where I get stuck and then I'll probably refer to the explanation.
So, if we've got like 52 52 cards and we've got four suits, which is going to be 13 13 cards every time we pick a card.
I'm steering into probability here, which is not where I want to be.
Um, okay. So each time we could pick one of four.
We got four four choices. If we're just ignore just ignoring the the cars themselves and thinking about the uh suits only.
Wow. My intuition is not taking me anywhere with this question.
Let me think about it differently.
Let's let's try and simplify it. Let's say we've got um let's say we've got Wow. Nothing at all. Okay, let me read a little ahead and see if I get any hints where the first entries. Okay, such a hand described by a length of len sorry a list of length two of the form this.
Okay, we could describe it like that, I suppose, where the first entry is a two element subset of the set of 13 club cards.
Right.
Okay. So, so there's one way we could do this then occurs to me. So, we could do uh 52 Oh, terrible numbering there. Let me do that again.
52 choose choose five.
And this is the total number of possible hands.
And then we could work out how many times can we do 52 choose. I know you're giving me hints in the chat. I'm not looking at them.
Uh, but thank you. A 52 choose. Well, I actually don't know you are. You might not be. You might just be hating. I'm sure you're not. A 52 52 choose two.
Where?
Uh, no. I'm getting nothing. I'm getting nothing.
Why is this confusing me so much? How interesting. My brain's just slow today.
Or is it an unusual question? I don't have a recipe for it in my head. The second entry is a three element subset of the the set. Okay. So where the first entry is a two element subset of the set of 13 club cards and the second entry is a three element subset of the set of 13 club cards. Uh sorry heart cards. There are 13 choose two choices for the first entry and 13 choose three choices for the second.
So by multip by the multiplication principle there are 13 choose 2 by 13 choose three such lists if we were choosing Wow that's just the end it's just the end is that it wow that is that is does not seem that does not seem like it should be it you know you know what I think it is I I think I'm getting pulled in.
I'm getting pulled in by the notion of trying to work out the probability of that happening. That's what I'm really getting pulled in by. That's why it feels like that can't be the answer because I'm not thinking about counting.
I'm thinking about what's the probability of it, which is not the question at all.
So, if we if we had a deck of cards and we could look at every card like they're all face up, the question is if they're all face up, how many different hands because it's the hands that's confused me because I'm thinking of like the chance in in like poker poker or whatever.
If we had all of the cards face up, how many possible hands could we make based on just picking the cards as we liked? Really, we got nothing's preventing us from picking them. The question is counting counting them.
That's what was uh that's what's troubling me on that one. So, given that, we we don't even need to worry about the other two suits. Like, we can just throw those away because we don't care about them.
We're only choosing and if we were doing this for real, we would just put the the clubs in one section and the h and the hearts in the other and we just pick pick from them, right?
Yeah. So, I'm just being pulled in the wrong direction for this. Okay. Interesting. I won't work it out because there's no point now. But interesting. Okay. What uh what's what's chat saying?
Rain intensifies. Yeah, thunder and lightning today. We got some thunder and lightning yesterday actually where I am.
Redeeming a mayasma of death and disease for channel points. Wow.
The probability of it happening is always the number amount of hands divided by five factorial. True. Yeah.
In a climb bot says, "Yes, this is the correct logic. The probabilities drawing such a combination will be the number divided by all possible five card draws." Yeah.
H interesting.
My intuition will have to mature on this.
Okay. Example 3.15. A lottery features a bucket of 36 balls numbered 1 through 36.
Six balls will be drawn randomly. For $1, you can buy a ticket with six blanks. You fill in the blanks with six different numbers between 1 and 36.
You win $1 million if you choose the same numbers that are drawn regardless of order. What are your chances of winning?
Well, this one even though it it is about probability this in this case um feels more obvious. Let me see if I can convert feels obvious into a correct answer.
Okay. 36 choose six and then it'll be uh one over that. Right.
Let's put a little hat on it.
I think and let me let me work out 36 choose six just to get my memory on this.
Okay, so it's n factorial over 6 factorial multiplied by n. What? That's 36.
uh minus 6 factorial.
Let's see if Python will uh play ball today.
So, let's try and do this in one. Well, actually, let's let's let's see it.
Let's just look at it.
Wait, actually, do I just have factorial now? No.
Let's just look at it. Oh, such a large number. Delightful.
Uh, math factorial 6 multiplied by 36 - 6 that.
Okay. So, we've got one 9 4 7 7 9 2 which is not six digits because if it was I would choose that number.
Okay. And that is the correct answer.
Great.
Let's get some color back in here. Okay.
Good.
Oh yeah, I got to float. I got to float again.
The book may cover arrangements. Oh, permutation. Is that is that the same thing? I suppose it is.
Yeah, if it is permutations, it was covered uh covered in the last session I think and the notation you're talking about which is uh a is it do you mean like uh this or is it or is it this? I guess it probably is the first one.
Not familiar with that arrangement that um notation.
Okay, I will I will um I will redo this with a uh double so that we don't have don't have floatingoint numbers on the screen.
Terrible.
We don't want that. Did you know that uh John Bakus' speed coding system uses essentially the same floatingpoint uh system as JavaScript does today?
I just assumed it would would be different. I don't know how it'd be different, but yeah. Well, not not exactly that. I don't actually don't know if it was standardized. Um, it probably wasn't standardized at that time. I E754.
Um, yeah, something quite similar to that.
is saying it's the number of ways to select and arrange k distinct elements from a set of n distinct elements. I think that's the same that's the same thing as in this book. I think it's uh k permutations which is notated as I think it's this which actually I don't like as notation so I I prefer prefer yours.
Yeah. Bakus predates um it le 754. It makes sense. Did you know um I learned I learned an interesting fact about um John Bakus yesterday which is that uh I think at some point he maybe in one of the world wars guess the second he had a skull injury and they put a metal plate in his head.
This is before he was a software engineer, by the way, before he was a programmer, I suppose. Uh, and he didn't he he felt it was not quite right. He felt it was a little looser than what he would want it to be.
Um, and so he just designed his own. He and he got someone to he got someone to fit it for him.
Interesting. Interesting guy.
He was doing a medical degree, I think, because he was he he did well on a medical attitude test when he was in the army or something like that.
Real real interesting anecdote that one.
Okay. Binary strings have an odd number of ones. Okay. This one seems not obvious to me.
Okay. How many seven-digit binary strings? Now that will be uh two to the seven, right?
Or is that is that wrong?
Is that just the number it can is that just the number it can represent?
In theory, there should be one arrangement for every arrange for every number in that range or is it 2 to the 8 minus one? Let me let me do this another way and work this out.
No, it'll be two to the 7. 100% it will because it's because we've got uh if it's one digit, it's two, which is two to the one.
If it's two digits digits, it's two to the two. And that'll be four arrangement. Yeah. Yeah. Okay. I don't know if that's how I was supposed to work it out, but okay. So, that's the total number. And how many seven-digit binary strings have an odd number of ones?
Okay, so the odd numbers in that range will be one, three, five, and I guess seven.
Now for seven there's only one there's only one possibility which is one one one one one for Five.
I'm struggling with the idea that we don't have we don't know uh we do know the number the total number of ones that we have to select.
I guess you know what it is. It's it it'll be it'll be the permutations of No, that doesn't make sense. I was thinking it could be the permutations of like this string, but that's not right because all the permutations of this are identical for for our purposes.
So again, wow, my intuition is not is not helping me at all.
Okay, let's look at this one. So here we we could have uh we could have zero zero z 0 0 1 or we could put this one in any of these positions. So there's going to be seven possibilities here.
Now what does that relate to?
And then we've got one possibility here.
I mean this would be the same as 7 choose 1.
And this will be the same as seven. I'm just noticing this. I don't know exactly why this is yet. 7 choose 7.
So, you know, following the pattern, we would expect this to be 7 choose three and this to be 7 choose five.
and then we get all of the all of the um different possibilities.
So if we add all those up, we should get the right number.
Now why is that? Seven choose three ones.
It doesn't seem right. It doesn't I mean it seems right, but it doesn't make sense to me. All right, let's find out what the actual answer is and then we can build my intuition on why that's true.
No, it'll be uh do we have choose here or choice? No. All right.
uh let's just take this as summed and we'll see see if the answer is something like this.
Okay.
Let A be the set of all seven-digit binary strings with an odd number of ones. So the answer will be cardality of of A. To find A, to find cardality of A, we break A into smaller parts.
That's the addition principle. We saw before, right? Notice any string in A will have either 1, 3, 5, or seven ones.
Let A1 be the set of seven digit binary strings with only one. Yeah. Fine. So, we're indexing the sets.
Yeah.
And we union them. So, we add them.
Now, we must compute the individual terms of this sum. Take A3, the set of seven-digit binary strings with three ones. Such a string can be formed by selecting three out of the seven positions.
You know, something my brain was saying it was something to do with positions. I don't know why I didn't follow that.
Three out of the seven positions for the ones and putting zeros in the other.
Okay. So, so we're selecting and let's call this one 2 3 4 5 6 Wow, terrible. And seven.
Um, okay. Okay. And so we're selecting we're choosing three of these positions and putting ones in them.
So then we've got how many different ways are there to choose from seven possibilities? That's the position. Three of them.
Okay, that makes sense. So, we're choosing positions in this case.
Okay. So, we we get that and then we add them together.
64. Fine. Well, I believe that.
Okay, you're choosing name that many zeros to replace with ones. Make sense? In a client bot says, if you think of it like this, each binary string defines a subset of a set with seven elements by selecting the elements whose positions correspond to a one. Then you look at the combinations. Oh, it's math domath.com. I see.
Now, suppose you swap all the zeros and ones. What do you observe that?
Uh, I guess we've got uh we've got um two other we've got uh zero 2 4 and six.
This kind of seems like it should be should be the opposite, right?
Okay.
Right now, we got some exercises. I should probably do these given uh Where am I typing?
Nope.
Nope. Okay. Need to work on my software.
No, there we go.
Okay. Need to change the foreground color. Um, right. Okay.
Suppose a set A has 37 elements.
How many subsets of A does 10 elements?
Uh how many subsets of A have 10 elements? How many subsets have 30 elements? How many have zero elements?
Okay. So, for this one, we are going to be looking at Come on.
We're going to be looking at Okay, it'll be 37.
No, wait. How many subsets of A have 10?
Okay. No, it is. It is. So, it'll be 37 choose 10 or 30 or zero.
Let's call that one or yeah, basically that.
So, with zero elements, well, actually, let me let well, I guess I'll just work this one out. That's fine. I'll work it out given um we may as well get some practice in it.
So this is going to be 37 factorial over oh okay 10 factorial multiplied by 37 minus 10 factorial which we'll just work out.
This one won't do all of them.
Wow, my laptop is really not happy.
It's too warm for it.
Uh, we've got Yeah.
Uh Whoops.
Okay.
Okay.
Okay. Oops. Sorry. Got the uh slashes wrong again. Okay. Is that right?
Okay. Fine. Let's have that be my numeric answer for that.
That's going to be three 4 8 3 0 1 3 6 need to work on my handwriting in this system.
Okay. Now, how many have zero elements?
That's going to be zero. No. One. Got to get that one right.
One. The empty set. Okay. Let's do the odd number ones.
Okay. Is there anything I can do with my computer to cool it down right now?
Open the most intensive system on my computer, which is the activity monitor.
Okay, maybe I can uh just sort this out.
Okay, that's slightly better.
And then close this. And just close this other tab as well.
Okay.
Right.
Are you running a local LLM? That is that is rough.
You'll need to play pay anthropic more money instead I think or open AI depending on your persuasion.
Uh or somebody else other AIS are available. Okay. Um three. A set X has exactly 56 subsets with three elements.
Set X has exactly 56 subsets with three elements.
Okay. So, we're saying that something choose uh three is equal to 56.
this should be relatively straightforward once we've got there.
Now, let's expand this out.
We should have uh in factorial over 3 factorial n - 3 factorial equals 56. Six.
What can we do? We can multiply by three factorial, right? And three factorial is 3 * 2 * 1. So that's six.
And then we'd get to Yeah, we get to n over n factorial over n - 3 factorial would equal uh what's 56 over 3?
Oh, that doesn't sound good. 18.6. six.
No, sorry. Divided by six. That's 9.
That's even worse. 9.3.
Let's just keep it in some sort of form, I suppose.
Maybe I'm wrong about this.
Well, let's make this six.
Uh, and then this we can also replace with six.
And then I then I then I don't know what to do.
Oh yeah, true.
Good point.
Dexter, hello.
I did make a video on edge.
I did not divide both sides by six.
Oh yeah, I multiplied them by six, didn't I?
True.
Good point.
Yeah. So, what we're actually doing, what we're actually looking for is this over that's too big.
N minus 3 brackets. Oh, terrible brackets.
factorial and then it's oh gosh okay 56 multiplied by 6 336 There's probably some I can do. Well, there must be something I can do with the left.
I'm just thinking so if we if we were to expand this what we end up with is we end up with so this is going to be like n * n -1 * n - 2 in the fact I think that probably is it but it would continue right and then we're dividing it over you know that subtracted so I think what we end up with is yeah because we're dividing by everything from n minus 3 downwards so I think we can just get rid of that and then I think we end up with this I might be slightly wrong here but I feel reasonably sure this is the right idea Yeah.
Saying there's no analytical way of solving this. I think Robon says I think a good observation to start is that the left hand side is a product of three roughly equally sized numbers.
I suppose so.
It's not just any cubic equation.
Okay.
So, well, we probably just Yeah, we could just probably figure this out, right?
It'll be close to it'll be approximately n cubed, right?
So we could look for n cubes that are that are close to this.
We have this to do this here. Or do we have something? I forget which language is like that. No, it's JavaScript that's like that.
Not quite.
Okay, that looks about right.
So it would be if it was seven, we'd have 7 by 7 - 1 by 7 - 2 to 10.
Not quite right.
Should we try eight?
Great.
Looks like it's eight.
eight.
Okay, interesting.
Thanks for the tips everyone.
Um, right. What we on? Three.
Let's look at five.
How many 16 digits How many 16-digit binary strings contain exactly seven ones?
Now, we looked at something like this before, right? And it looks pretty similarly shaped.
So, we've got 16 positions and we want to choose seven places for the ones, right?
So, we've got 16 choose seven probably.
What a beautiful eight. Thank Thank you.
Thank you. Put that eight back on the screen.
Yeah. You know what? You know what? The thing that gives me the ick is seeing someone seeing someone with an upside down eight.
Like uh like it's bigger on the top.
Terrible.
Um okay.
No, that's not three. Why have I put three there? Wow. Hammet. It is.
It's hot today.
channeling that guy from the Simpsons seven.
We've got some notation here.
uh the cardality of the set where x is an element of the power set of this set of 10 digits 10 symbols that just happen to look like digits where x where the cardality of x is less than four. I suppose if we were doing the even nons that would be um we'd have already worked out the cardality of exactly four. We can use the addition principle for this.
So let's do that.
So we're going to work out the cardality for 0 1 2 and 3. And that will be we've got 10 digits there. So, it's going to be 10 choose.
Let's go three.
Yeah, we'll have those sets in there.
And then we'll just do a little uh do a little dot dot dot 10 choose zero.
Yeah, I think so.
It is. I'm excited for get for it to get cooler.
again. Always excited for change. Okay, we got the eight, we got nine. This problem concerns lists of length six made from the letters A B CDE E F without repetition.
How many such lists have the property that D occurs before the A?
Okay, interesting.
So for this one list of length six made from the letters A B CDE E F.
So we could work out D occurs before the A. So we could like enumerate all the lists possible where D occurs before the A and then we could work out how to count those.
Now, those would look like um with the D first and then it would be we'd have some here or we'd have um Yeah, we'd have we'd have Yeah. And this would be nondes crucially or we could have no in fact let me let me make this a little bit more three four five and then at this point this would be this would be a set this would be for a set of five symbols. It's always actually going to be five because we know the D is in there.
Or we could have one blank space which could have one of five symbols in.
No.
And then a D.
That's not a great T.
And then one, two, three, four, five, six.
And then here we could have one of four symbols in And then we could do the same for the D being being here and the D being here and the D being here.
And we couldn't ever have it here.
Or actually, no. For for here it would have to have the for here it would have to have the the A at this point.
So that one be that one would be special.
No, actually that wouldn't even work because if we had let's say if we get rid of this. Let's say if we had the D here.
In that case, we'd need to we'd need to make sure that we had an A in one of these two positions and we wouldn't have an easy way to do that. So, I don't I don't think this way is going to work.
introduce something else.
We could try and do it with positions.
Maybe maybe that would work. We could choose We could choose two digits.
So, we've got we've got six digits and we want to choose two. And we know they're not going to be the same.
If we choose two digits, let's say we choose two and three.
And let's say we have a rule. We always put the D on the lowest of these two because it'll be a set. So, we won't care too much about that.
And then this would represent this sequence.
So this would help us then work out how many different positions of DNA we can have.
And then we just need to multiply this by the number of um permutations of the other four characters which will be the same because we're going to have DNA in it in in general.
So let's figure that out. Um, so for for the four other characters, let's call that um uh let's give a number for that. Let's let's call this I don't know G.
Let's choose a letter.
Uh so that that's going to be um four factorial, right? It's just going to be four factorial because we're just looking at arrangements of permutations of four symbols across four across four um places. So we're not dividing anything out and so we don't need to worry.
So that'll be that. And then the other side of it is going to be the number of positions that we can have DNA.
Uh let's call that uh B. I don't know. It's probably the right letter to choose. A right letter to choose rather.
And that's going to be six possible positions.
Choose two.
That'll be the number of positions we can have. We don't need to worry about order in this case I don't think.
So I think the answer will be 6 choose 2 multiplied by 4 factorial.
Okay. Interesting.
Go in 42. You're working through Book of Proof right now as well. That is cool.
That is cool.
Uh, I'm in the briefcase says, "Did you see the new James Bond game?" What an unusual question.
Apparently, it makes one of the most boring parts of video games fun. Why'd you ask? I hadn't seen it. Haven't seen it.
Okay, final answer.
All right, 11.
How many positive 10-digit numbers contain no zeros and exactly three sixes.
Now in that case, so no zeros. Let's say if we just wanted to work out no zeros, we could have uh the permutation. No, wait.
If we just wanted to work it out with no zeros, I swear these problems were easier last week. Uh, how many positive tangent numbers contain no zeros?
Okay. So if we had that, let's say we have a set of the digits one to nine, but we're going to have a repeat. That's what's tripping me up.
Yeah, we're going to have a repeat in there. So, we're not we're we're going to have to use a slightly different method, I think.
So if we had if we if we were thinking about this as we did last week first we could choose the position of the three sixes which we could say could be calculated by having so it's 10 digits so 10 positions and then we can choose three of to choose the the positions of the sixes. That would leave us with seven other digits.
And the seven digits that's going to be and and there so we got seven other digits and they cannot have they cannot be six and they cannot be zero. So that's going to be eight possibilities.
Yeah. So we got 10 digits.
nine without the zero, eight without the um yeah. So it's going to be 8 to the power of seven.
Yeah, because we're choosing Yeah, that's I think that's right.
no zeros. So, we don't need to worry about that.
Yeah.
Okay. So, that's 11. Let's look at 13.
Want some more rain noise?
There we go.
Okay, let's look at 13.
13. Suppose that n and k are in the integers and k is between zero and n inclusive.
Use fact 3.5. the formula n choose k equals etc to show that n choose k is equal to okay it's just got louder okay too much rain too much rain too much rain okay to show that n choose k is n choose n minus k okay interesting I sense I'm going to have to do some arranging again.
Oh, it's really rainy, right?
Oh, so it's basically just asking us to to prove that or not prove but to show that um something like uh let's say we had five choose oops five choose two.
This is going to be equal to five choose three.
Now I seem to remember there's some there's some uh uh like triangly distribution of these chooses.
So there's there's there's one five choose five. There's so many five choose three. Sorry, five choose four. There's so many five choose three.
There's so many five choose two. There's so many five choose one.
There's one five choose zero. So there's that sort of relationship here. I seem to remember that that's true. I suppose it's asking us to show that in some way. Okay, let's try this out.
Slightly out of my comfort zone on this.
So, we know the top's going to be the same regardless because that's affected only by n.
And we want to somehow show that. Okay. Actually, maybe this is we could just substitute this in.
The fact they've chosen K is is not going to make things easy, is it?
Okay.
Well, let's write this out anyway.
Okay. Okay, so we've got n in here and we're going to have k n minus k.
Right. And now if we substitute these in, if we substitute in this n minus k for k, what do we get? What do we end up with?
And in fact, let's let's let's even get rid of this, right? We don't we know that this is going to be going to be here. So hopefully we don't need to worry about that. Well, we're we're going to try and just deal with the bottom bottom half. Okay. So, if k is n minus k, then what we end up with is n minus k.
So, it already looks great.
Here's where it goes wrong. Right. Or right. Wrong.
Now this is going to have n minus k minus k.
So, we need we need this to end up being K maybe, which it looks like it probably will maybe.
We don't need those brackets.
Sorry, I've messed that up. I've done that wrong.
I'm sure you're probably you may be saying that in the chat right now. Uh, okay. Where were we? Where's my colors?
That's right. So, it's actually in I substituted the wrong thing, as you probably realized.
n - n minus k. Now that looks more promising because n minus n gets taken out and we got minus k in there.
Well, we can take we can take the ends out anyway.
And then we've got minus k factorial.
So this kind of this ends up getting rearranged to maybe this minus k is some sort of some sort of problem.
Brackets matter now. They're saying they're saying brackets matter now.
Okay, let me let me try this again.
Uh, no.
Okay.
Oh, good morning. And Stucky, how goes the art?
Um, the art is I'm getting I'm getting to the art.
You know, I learned something. I realized something.
Somebody uh after all of this dealing with induction, which which I found a little challenging when we were working through Canuth's Canouth's book, I saw a random Reddit post about someone complaining about induction and I was like, wait, that makes perfect sense. So now, now I feel like I feel like I got it. I got it in that second when I wasn't actually doing any work. So, I think it's going well.
Okay. All right. Where we at?
How's it going with you and Stucky?
It's ends. Sucky actually. I apologize.
Okay.
Right. So with this you I mean the brackets do matter here. You're right.
So with this we can um change this to n plus minus one by I think you can do this.
It's been a while. It's been a while since I've had to do any of this except when I'm working out coordinates. It doesn't usually get this complicated. In which case we end up with n plus uh and this ends up being k minus n.
No, that doesn't look good.
Maybe it maybe it'll be okay still.
Okay. So then it's n + k.
This is where for some reason this is where people who know math come to torture themselves by watching me do elementary operations poorly. Okay. N minus n is nothing. So we get k. So therefore therefore I think you'll find It actually it's actually the same thing after all apart from where you can put this K on here and then uh it's the same apart from not not that there. That's not the same. Uh, it's actually it's it's got to go here because that was always on the outside.
Remember that was always there.
Q E D strandom.
Okay. What's chat? What's chat saying?
Um, Climbot says, "Induction is quite easy once you get your head around it. I don't miss writing out transfinite inductions up to the first uncountable ordinal, though. Me either.
That was tedious. It sounds tedious."
And Stucky says, "Morning's going great." It's morning for you. Amazing.
Happy morning. Oh, good morning. That's what we say, right on Earth. You have a quiet day today, so it's going to be a lot of enjoying the math twitch verse.
Oh, great.
Amazing.
I um not that anyone asked, but uh I I I lift weights and I went to the gym this morning and I had a great had a great time. I walked in and a a an impressive looking man uh came up to me and he said, "Kay, of course you're here. Of course you're No, he he said, "I've lost my phone. Could you ring it for me? Would you mind?" And I said, "Of course." And I rang his phone and then he found it and then he just chatted a bit. So um that was good.
In a climb says, "Trult is not right.
Actually, it's quite satisfying as a teacher and not in a weird way to see that moment when someone starts to understand things for the first time.
Yeah, that does. I I I I can agree. I can agree with that. Missing a factor after the K. Yeah. Oh, yeah. The other K.
Okay.
Terrible.
Oh, thunder.
Oh yeah. Oh my gosh. Convoluted way to get your phone number. True. Oh my gosh.
I was play. Oh my gosh. This is what CL this cl this is what you were saying.
Isn't it satisfying to see the when someone understands something I don't think then played.
This is just like the shutdown script again.
No, I don't think that was it. He didn't he didn't seem like he was like he was way out of my age bracket and I Yeah, I Yeah, that wasn't the vibe, I think.
Oh my gosh. All right.
Okay. Pabon says, "You can apply inductive reasoning to weightlifting by proving you can lift 100 grams more yesterday than you could today than you could yesterday."
I I I I hope to prove that one day, but not yet. I haven't proved it yet.
I had a good session today though.
Um, I don't get to talk about it very much. I say that I talk about it all the time. But I do love talking about uh weightlifting. I became a real gym rat over the past couple years.
Um, and I would uh can anyone does anyone want to speculate on what I was doing today?
What my what my movements were today?
Probably not. Dull conversation, but I just can't stop talking about it.
Oh, yeah. Yeah. Lift the universe.
That's true. That would be pretty good.
Where was I? Okay. Uh, yeah. Did that.
I have to factor in death. Oh, no. True.
I have to prove that I can't die.
Let's hope I can prove that as well.
Okay. 15.
How many 10-digit binary? It's a binary strings question again. How many 10-digit binary strings are there that do not have exactly four ones?
Well, that'll be one minus. No, not one minus. That'll be the number total number of binary strings which will be 2 to the 10 2 to 10 2 to 10 2 10 2 10 2 ^ 10 2 raised to the 10th ordinal I don't know two 2 uh minus those that do have exactly four ones which we know how to do because I've been I've had that drilled into me Ready?
So that's two to the This is lagging. Need to work on the performance of this Telustrator software I've built.
Oh, terrible. Okay. 2 10 minus we've got four pos four positions to put a one.
No, we've got we've got 10 positions and we want to choose four of them to flip as somebody was saying earlier.
Okay, great.
The computer scientist sick of sick of binary strings. I see how it is. Yeah, that's true. That's true. Badon, I um I'm sick of binary strings. You know, I want to go back Let's go back to the way things used to be. Let's go back to decimal computers.
Um I'm sick of this binary nonsense. I want to I want decimal computers. Let's go back to the uh let me quickly Google this.
I think uh one of the earliest Yeah. Eniac. Let's go back to the Eniac.
The Eniac. If it was good enough for um whoever was working on the Eniac, it's good enough for me.
Was it using the Manhattan Project? I think it No, it wasn't. Maybe it was.
Oh, yeah. If it was good enough for the Manhattan Project, it's good enough for me.
Let's go back to the electronic numerical integrator and computer.
Actually, let's probably not let's not let's not go back to that.
But still still need to make that uh make that video about libnets's obsession with with binary numbers. Leninets lieets.
Okay.
Hackers delight. One of the engineers I worked with last year introduced me to this book of bit twiddling tricks called Hackers's Delight. That sounds great.
Drop the link in the chat if you have it.
Okay, that's 15. Uh, I went to scroll down.
It doesn't Oh, okay. Thought there was more exercises.
We're almost there.
17. How many Oh, how many 10-digit binary strings haven't No, wait. 17. How many 10-digit binary strings are there that have exactly four ones or exactly five ones?
How many do not have exactly four ones or exactly five ones?
Okay. Well, that seems trivial, I think.
So, if they have exactly four ones, well, actually, we don't need this. If they have it, if they have exactly four ones or exactly five ones, Then it should be 10 choose four. Probably maybe he's expecting us to calculate it out rather than just like lazily do this. Maybe that's why I also do feel like um this guy has a bit of a habit of uh putting the difficult questions in the middle.
Uh notice that a couple times now.
Minus this I think.
Amazing. Thanks for the link and a climb ball.
That sounds cool. Love to learn some binary binary bit twiddling tricks.
I just can't help with that. That's too That's too scruffy.
I need to get my uh Apple Pencil hooked up to this thing.
Oh, that's a good point. That's a good point actually. Is it Is it the same?
Okay. 1719.
A five card poker hand is called a flush if all cards are the same suit.
suit is yeah clubs or whatever. How many different flushes are there?
So in this case we've got 13 cards in a suit.
So it's going to be 13. the number of ways we can choose five cards from 13 cards times four because there'll be four suits, right?
It um it will be really awful studying maths I feel if you weren't familiar with like playing cards or worse if they were like um like illegal because they're I think some religions don't uh don't don't let you play with that stuff.
I suppose you can still answer the same questions.
I once I once dated someone who who um had I think had I think I think she did she was she did play with playing cards, but I think she like maybe wasn't supposed to or something.
Maybe I made that up.
Okay, so 13.
Choose five, I think.
Okay, great.
Soon we will look at the answers, but I'm going to take a short break before we do that.
So, you get to listen to some rain sound and I'll be back in a few minutes.
Ah, I would love I would love some of that sound outside right now. Back soon.
Oh, it got really loud, did it?
It's so loud. Sorry. There's a part where it like gets really loud.
Um, no. It probably wasn't your fault.
Uh, I noticed that uh, Soding Soding does this thing where um, he puts his tea on and then he comes back and chats while the tea is steeping. I think I'm going to try that today.
So, uh, anyone know any good jokes?
It's probably because, you know, sing streams have like 1 billion viewers. So, any question?
Um, any question there's an immediate answer.
How do you feel about the cover of princ of compilers principles, techniques, and tools? How do I feel about it?
There's a bunch of them, right?
They they they um so I think the old one with the red dragon.
Yeah, the the the CGI one is my my board is not is not competent enough to uh to show this to you, but um the the new one freaks me out.
The new one with the with the CGI dragon freaks me out. I like the I like the red. I like the one where um the dragon is green.
The green dragon is good. The red dragon the red dragon's a little aggressive.
I don't feel like the the the I think the the whole point of it is that the book the the ideas in the book are supposed to um help you slay the complexity of compiler design.
Um but it feels to me like Uh, the one the one with the red dragon, he's not really he's not he's not slaying anything.
The dragon is in his computer.
It's not right.
Uh whereas the green dragon book, he's slaying that. He's slaying that 100%.
Okay, this is the green This is the green dragon one. I'm going to I'm going to put the a link to the green dragon one. That's the green dragon.
And then if you don't if you don't know, I'll put a link into the red dragon as well. It's an Amazon link.
Now, tell me the red dragon is being slain.
That red dragon is in control.
That red dragon has has put his head into the computer.
Now the green dragon, the green dragon is he looks fraught. He looks like he is he knows that he's in danger.
Maybe it's a different book. I think I think it's the same book, but I think it's the additions might be quite different. It does look actually kind of different now.
I I think I think they're in the same universe anyway.
Yeah. So, I'm feeling the green dragon is the green dragon's the one even though the green dragon I think is the most outdated.
I'm very excited to at some point get to the point where we talk about the fact that Canuth um can uh he did the LR LR he did a whole bunch of stuff in passing the LR paraser all that he did a whole bunch of LR passing that now now people um it was like I think he got he got nerd sniped by um better passing But now it's like it's not it's not the I mean I don't understand the work well enough to to to say but people don't really use it as much.
I think that's an interesting interesting thing that he spent spent his time on that.
Lexi T says, "I'm currently reading the C programming book as well as some game engine development books for more performance work." That sounds cool.
What are you working on? Oh, there's a question. Any advice for finding work in low-level systems? I spent 15 years in full stack. I want to pick up a job in the lower level, but I'm 12 years behind on lowle ability. Unfortunately, I have no advice. Um, I have no advice on that question other than stuff you would have thought of already. Um, as I've not had a job in lowle and don't don't actually know anyone who's done I know. I know I've I've met people who did low low work.
Um deep knowledge of the language seems to be a common amongst them, but I I I don't know. Um I don't think I have any advice that I would say and know that you should trust me to give you good advice. Like don't trust anything. I wouldn't trust me to give advice on that question. So I won't I won't uh I won't give any. But I you have my support. That sounds like a brilliant um path to go down. Um and just yeah, keep learning that advice. I I do rate compiler theory probably. Yeah, compiler. Oh, you're looking at like low-level like compiler theory stuff.
Oh, that's cool.
That's cool.
in a climb bottle seems to be a sea hater, but um do I have anything to say next? I don't think I do.
See haters.
Um are we pro or against C in the chat?
What do we say?
Any vote? Anyone? Anyone want to wanna want to vote proc is is a sea hater. However, um also can't open uh their marmalade.
So clearly a modern language doesn't help with that. Doesn't help with everything.
I was actually thinking of of taking on a C project reasonably soon, something significant because I feel like I've feel like I've just played around with it, but I would like to I'd like to get really I'd like to build something more serious.
No disguises. True.
some I read somewhere that you can basically write C and assembly macros if you're like really if you if you want to like torture yourself like that but it's basically possible.
Uh, I don't know if that's true or not, but it could be register keyword pleasing.
You know, in the fourth community, they they refer to um all all nonforth languages as C basically.
To us, to them, we're all C programmers, which is very it's very funny. Like they'll they'll refer to something as like C or C C programming stuff and somebody like, "Oh, no, that's not C.
That's that's JavaScript." And they're like, "Well, that's C to us.
which makes sense. I mean they kind of like forth diverged diverged um from mainstream let's say the mainstream programming uh culture like before C or or in contrast to C.
Okay, I'll be I'll be back. I'll be back in a in in a in a two minutes. Two minutes.
Okay, I've returned. Everyone's still friends, right? Nobody's falling out of a sea.
Okay. Right. Let's see. Let's see how many I got wrong, shall we?
Okay.
3.5.
I don't want to use the find find tool anymore.
Heats my laptop up too much. My laptop laptop needs a break.
Lexity says there's been a civil war between pre997C and post 1997 C.
Huh?
That sounds interesting.
Okay.
Right. Now, where were we?
Uh 348 136. That seems right. And then one and then the thing in the middle. Uh I'll give myself a come on. I give myself a tick for that.
I didn't do two obviously. I did three.
So a set has exactly 56. Okay. What do we get? Eight. That one was that was a challenge. Thank you to everyone help who helped me with that.
Five.
Uh 16 choose seven. Great.
One. Okay. What's this supposed to be?
Choose. Yeah. 10 choose zero through 10 choose three.
Okay. Great.
9 uh 360 that's uh yeah 6 choose 2 by 4 factorial.
Yeah, I think that's right.
And then for 11 10 choose three. Okay, fine.
Then 13.
Sorry, 13 is well, I think it takes a similar approach to what I took.
So I think I'm going to mark that roughly right.
15.
Is ffmpeg still written in C? I was just wondering that actually.
Is that still written in C? It seems like it should be. 2 10 - 10 choose 4.
Okay, great.
And then it's 17 is uh yeah that's right and then 19 is yeah I feel like they might use inline assembly in that feel there's a lot of portability stuff that happens with ffmpeg for that reason.
Okay.
13 choose five.
Yeah. So, it's four times. Great. Okay.
Let's call that a Wow. Amazed I got those right. Those were those were kind of tough.
Those were kind of tough for me, but that's the point of them.
Right now, we're going to learn about some sort of triangle. Now, I want to warn anyone who's afraid of triangles that there are some triangles in the next section.
So, be aware. Oh. Oh my gosh. Okay, there they are. Yeah, we got some triangles coming up.
Okay, let me uh let me just cut into my terminal. Actually, that's going to end everything.
No, I won't do that. Let's see how Let's see how much my laptop can take.
Okay. Watch out for the triangles. Check 94's got one of the great triangles out.
Yeah.
Okay. Triangles.
Let's go.
Any thoughts on the um on the on the new whiteboard setup? It's a little laggy.
I want it to be smoother than that.
Anyone got any thoughts? Do let me know.
Still working on it actively. 3.6 Pascal's triangle and the binomial theorem. There are some beautiful and significant patterns in the numbers n choose k. We will now investigate a pattern based on one equation in particular. It happens that n + 1 choose k is equal to n choose k minus one + n choose k. Interesting.
for any integers with n and k with k between one and n in says the smoothing is a little aggressive. Makes it hard to write small stuff. True. I need to fix that. Need to sort that out.
Bubbledon says instead of useful features, you should add a Vtuber style face tracking so you can draw symbols on your face and they move with you. Now there you go. I could be a VTuber. I could I could meet my VTuber dreams.
Maybe I am already.
Maybe I am already.
Uh CH4 says, "Do you prefer the curve smoothing? I wouldn't bother with it." I do prefer it because um my fine motor control is not great.
Uh, so I'm trying to work I will I will I will I will improve it. I definitely will improve it, but I basically want something that makes it a little bit easier for me to write something relatively neat. This isn't quite working right now, but I feel like I'm in approximately the right direction.
So, um, let me just Yeah. So if I then one of the issues with this system is that currently smoothing is based on the number of points. So smoothing works in this in this library called perfect freehand by I think it works by simplifying the number of points um like a reducing the number of points basically um which is fine but what it means is if I if I do a a a fast movement which will have few cursor points like this it will simplify a lot whereas if I do um slow but a similar movement more points less simplified. Now I need to sort that out. It cares about speed indeed. It cares about the number of points which is caused by speed um or influenced by speed with a cursor.
So I need to sort that out.
But you should see my handwriting without any smoothing on. It's really it's diabolical. Anyway, the point is it should be clear.
Um. Oh gosh. Okay. Yeah. Need to sort that out. Need to get that fixed.
Anyway, so I I could have worked all this out of course before, but I thought I would test it live.
Okay.
Binomial stuff. Okay. For any integers.
So this is this is kind of odd, don't you think? It's kind of funny that that that's the case.
Let me try and think about that for a second.
So if we have maybe it makes sense. It's probably going to be like a side of the triangle, right?
That's probably what we're going to end up looking at.
Interesting.
Okay, let's read on to see why this is true. Notice that the left hand side n + one choose k is the number of k element subsets is the number of k element subsets of the set a is zero through n which has n + one elements that's acting as a filter Right?
Notice that the left hand side n + one choose k is the number of k elements subsets of the set of the set a where a is the set of the numbers zero through symbols 0 through n which has n + one elements.
Such a subset either contains zero or it does not.
The n choose k minus one on the right is the number of k element subsets of a that contain zero. Because to make such a subset, we can start with zero and append it an additional k minus one numbers selected from 1 2 3 through n. And there are n choose k minus one ways to do this. Also the n choose k on the right is the number of subsets of a that do not contain zero for it is the number of ways to select k elements from okay in the light of all of this equation 3.3 just states the obvious fact the number of k element subsets of a equals the number of k element subsets that contain zero plus the number of k element subsets that do not contain zero.
Equation 3.3 just states the obvious fact that the number of K elements subsets of A equals the number of K elements subsets that contain zero which will be now what is the number of K element subsets that contain zero um this And that's true because we're taking away one element which will be zero and zero is the same as anything else. So fine plus the number of K element subsets that do zero is only special here. Zero is only special because it's the only one that's guaranteed to be in this sequence provided that it's above provided that we're in some sensible range because you know three might not be in there might not be large enough okay k subsets that contain zero plus the number of k element subsets that do not contain zero and that is This part, this is the ones that don't contain zero.
It's the ones that don't contain zero because we've taken n down by one essentially.
So, we've removed one of the symbols really that we can choose.
Well, actually, both of these remove one of the symbols.
This removes Yeah. Okay. Weird.
Fine.
Okay. Having seen why equation 3.3 is true, we now highlight it by arranging the numbers.
Okay, let me get rid of that.
Arranging the numbers n choose k in a triangular pattern. The left hand side of figure 3.3 shows the numbers just scroll down again.
shows shows the numbers n choose k arranged in a pyramid with 0 0 at the apex just above a row containing one choose k with k 0 and k1 below this below this is a row listing the values of k 2 k 2 choose k for k is one 012 and so on.
Dexter, I have no I have no commands active, but you could tell me whatever specs is supposed to do and I could tell you they both remove zero as a choice because you've already made that already made the choice. Both of them from both of them remove zero. It is just a matter of picking elements either K or K minus one elements from what remains Kax commands. That's true. That's true.
Unfortunately, amateur hour here.
Okay.
This triangle is just for illustration, I guess. Oh, no. This is the count. This is the counts.
This is the result of n choose like 2 choose one is two fine.
Now this is um this is that that that uh that equation right.
But we know that's I already know that's how Pascal's triangle works, right?
So in this picture this is the number of ones the number of uh yeah so this is the number of ones two choose 0 and two choose one. Okay.
Where does this where does this come in?
Yeah. So, yeah.
So, I'll keep saying so until it makes sense. Always a good uh Yeah. So entries case on the right is the number of subsets of a that do not contain zero.
So this is the number of ones that don't contain zero and this number ones that that does contain zero do contain zero I guess maybe.
Okay.
Any number n + one choose k for zero within k and n exclusive uh in this pyramid is just below and between the two numbers n choose k minus one and then choose k in the previous row. But equation 3.3 says n + 1 choose k is equal to n choose k minus one and then choose k. Therefore any number other than one in the pyramid is the sum of two numbers the two numbers immediately above it. Okay.
This pattern is especially evident on the right of figure 3.3 where n choose k is worked out. Notice how 21 is the sum of the numbers six and 15 above it.
Similarly, five is the sum of the one and four above it and so on. This arrangement is called Pascal's triangle after I think it's blaze bla1 Pascal.
Correct me if I'm wrong. 1623 to 1662.
A French philosopher and mathematician who discovered many of its properties.
We've shown only the first eight rows, but the triangle extends downward forever.
The triangle extends downward forever.
We can always add a new row at the bottom by placing a one at each end and obtaining each remaining number by adding the two numbers above its position.
Doing this in figure 3.3 uh which I guess would be on the right if this was a real book gives a new bottom row.
Oh, in the right sorry the right triangle.
This row consists of the numbers 8 choose k for num for zero for k between 0 and 8 inclusive when we've computed them without the formula 8 choose k at all. Any n choose k can be computed in this way.
The very top row containing only one of Pascal's triangle is called row zero.
Row one is the next down followed by row two and row three. What comes after that though? It's kind of kind of weird. He doesn't doesn't explain what comes next.
Thus, row n lists the numbers n choose k for yeah. Exercises 3 513 and 3514 established this for each. Yeah. In other words, the kith entry of row n of Pascal's triangle equals the n minus k entry.
In other words, the kith entry of row n in Pascal's triangle equals the n minus kith entry. Oh, so it's symmetrical.
This means that Pascal's triangle is okay. So just read ahead. Don't bother thinking with respect to the vertical line through its apex as evidenced in figure 3.3.
And then we've got some uh interesting we've got some interesting things there.
Notice that row n appears to be a list of the coefficients of x + y to the^ n.
Row n appears to be a list of the coefficients of x + y to the n. For example, what what is he talking about?
Is this in any way? Is this in anywhere related to anything? Probably.
Just keep reading. Try and understand it. Okay. Uh, for example, x + y^ 2 equ= x 1 x^2 + 2xy + y 2.
Right. Okay. Okay. Wait, wait, wait, wait, wait.
Let's just zoom in on this so we can understand it a bit better.
Right. So this is this is one formula, not a bunch of formulas. Okay, that makes more sense, right? And this comput this this this evaluates to something.
It evaluates to x + y to the^ n.
Right? So, so this this this would be an expansion of this.
Is that right?
Yeah.
Yeah.
Okay.
Fine.
Well, that's that's cool.
Thank you, Isaac Newton.
Is that ring in the background chirping of that common insect? Let's turn it up.
There is a little Is this is still there if I mute myself?
I think it's I think it's in the in the in the sound. I don't think it's um in real life for me.
Probably probably something like that.
Posture check. Posture check myself.
Thanks Sam.
You can uh you can listen to it yourself. Somebody asked the um asked asked the sound the other stream and I can't where it is now. Let me see if I can find it again.
Every day I forget the sound.
Still forget it. It's on free sound anyway.
Okay. So, there's a triangle.
Yeah. Yeah. Yep. Yep. Yep. In fact, this turns to be true for every turns out to be true for every n. This fact is known as the binomial theorem and it is worth mentioning here. It tells us how to raise a binomial x + y to a non-gative integer power n.
Theorem 3.1 the binomial theorem. If n is a non- negative integer, then x + y to the n power is equal to n choose zero xn n choose zero n minus one. Yeah.
Okay. Y Okay. Right.
And then we fine. For now, we will be we will we will be content to accept the binomial theorem without proof. You'll be asked to prove it in an exercise in chapter 10. Oh, good. You may find it useful from time to time. For instance, you can use it if you ever need to expand an expression such as x + y to the^ 7. To do this, look at row seven of Pascal's triangle in figure 3.3 and apply the binomial theorem to get this.
Goody.
Wow, that looks horrendous.
Hello, Atom Fighter. How you doing? How uh how's the how's the fight against those atoms doing?
You managed to cut any in half yet?
They say you can't do that.
I know different.
This is why the numbers n choose k are also called binomial coefficients.
Thank you for the information botheron.
Yeah, atom fighter may be splitting atoms in Oh, you fight for the atoms not against them. Oh, I see.
Well, don't we all?
I suppose some may be some maybe fight against them. Maybe anti maybe there's an antimatter version of us out there.
Does antimatter life exist in the universe? Discuss.
Okay. Write out row 11 of Pascal's triangle.
This guy's a real joker.
Um, okay. Okay, row 11.
It's going to be some It's going to be like uh 0 choose 11, right?
0 choose 11.
One choose 11. Two choose 11. 3 choose 11. 4 choose 11. 5 choose 11. 6 choose 11. 7 choose 11. 8 choose 11. 9 choose 11. 10 choose 11.
11 choose 11.
There that's the answer. Um, use the binomial theorem to find out the find the coefficient of x to the^ 8 in.
Okay. Okay. Can I do this without doing like a million years of work?
Let's hope.
Okay. So, it's expanding.
Yeah. Okay. So, so we're saying x is x x is x and y = 2.
Uh and so if if it's the coefficient of 8 x8, so this is row five, right? We've got a we've got a x5, x4, x3, x2, x1, x0.
So, we want to be in row We want to be in row uh 13.
Let me write this down. We want to be in row 13. That's a terrible three. Sorry.
Right. Slower. Uh we want to be in row 13 and we want to be So, this is choose.
Sorry. Uh, so this one is x5 because we're on the first row.
So we want to be in term 13 minus I'm just being lazy here. I'm just just being lazy about it.
13 minus uh what's what's uh yeah 7 30 - 5. Hello Inda. How you doing?
Yeah. Okay. So, I think it's probably going to be 13 choose.
13 choose five maybe.
Sorry, you've come to the wrong the wrong stream if you if you don't want to see maths.
Good to have you here. But the math there is this a very math math heavy stream at the moment. It won't be forever.
Okay.
So, yeah.
13 choose five.
I really don't. I'm really getting I'm getting I'm getting tired. That's what I That's what's happening.
13 over math factorial 5 multiplied by 13 - 5 12 12 uh 1287 Why am I even doing this?
Why am I Why am I doing this again? Uh yeah, that's the coefficient, right?
If I've got that right, and there are several steps that I could have made it like an off by one or like a subtracted the wrong number, the kith entry of row n of Pascal's triangle.
So the kith entry of row n of Pascal's triangle yeah actually ends up being yeah the coefficients here and then we start off at five and we we start off at 13 and we try to get to eight. So we end up with the fifth fifth being our k or the fifth Yeah. Fifth being arcade and 13 being the Yeah. Okay. I've accidentally started some sort of conceptual debate about um antimatter versus matter in the chat. I apologize.
It's like info wars in here, but for uh but for random random questions. Um hello. It's really random.
Only ever done math while coming for exams, says Sam. Yeah, I mean I've only well I have I've done a little bit of math uh for programming purposes but not very much. But um you know I'm doing it for content now so I've got good motivation.
Uh is the maths massing today? It it firmly is. It firmly is.
Yeah.
It's definitely massing today. It's the math is beating me today. It's beating my ass.
If I was American, I would I might say that.
How's your day going? It's really rain.
It's getting rainy.
The Decker is saying, "Hopefully you can hear me over the rain.
Is this the mass that's used to make animations like those in reals or motion graphics?
Maybe. You know, it reminds me though, the reason the reason I picked up on that is it reminds me they um you know, three blue one round has has the whole man in like a video engine type thing. Mass visualization engine.
Um well, I watched this video the other day. I can't remember who it was by.
Apparently, they've they've they've AIed him. They're doing AI free blue one brown now. And somebody's downloaded manim and they've gotten they've gotten they've gotten an AI to write write all the write all the scripts. Um and they're just they're just generating they're just generating three blue one three blue one brown style videos and putting them on YouTube and they're all terrible basically.
But then the the comments in the comments of this video they were saying I don't really care if they're terrible as long as they're right. which I guess guess if you want to consume your facts about mathematics through the least efficient mechanism possible which is a random like a like a YouTube video where an AI has written some man incurred I guess you could do that I mean why not you know why not I shouldn't I shouldn't judge if that's what they like then then great but it is it's funny because you know if you're if you're blow and brown you're probably feeling like you've created did some you had some your your your invention of this mathematics library mathematics visualization library has really had some unintended consequences.
Um free artificial one.
That's good. That's good.
Uh it's really Ren says um I believe from your accent that you're from the UK too. Yes. And the country in the last few days has been on fire.
Uh, is the rain an audio track or IRL from the window? Is an audio track?
Um, I've posted the link before.
It's pretty good. It has one moment where it gets extremely loud suddenly just for laughs.
It's interesting at the moment with AI and making videos because the last the last video I I properly produced the idea you you'd get like some sort of like realistic AI video was was nonsense. Um and and now it's it's reality. Um and so I'm thinking I'm thinking I might develop like an AI colifon. Is that how you pronounce that?
Because, you know, I use when I'm writing code, I use like AI autocomplete and stuff like that. So, I can't really say no generative AI was used in in entirely in the production of this project. Some projects I can, but you know, it's it's it's 2026. Occasionally, I will consult um or I will I will get autocomplete running or something like that. But it's different obviously from, you know, just Wow, my keying is terrible today. Awful. Um, different from like getting the AI to make the video. So, be nice to have some sort of um proper disclosure there that was honest.
Dexter says, "It's summer here and we're melting. It's we're melting in the US, I guess, alive.
My skin get burns from the sun easily in two hours. Oh, terrible. Yeah, this is this is we're just we're just pretending that there's rain in this channel.
Deca says, "Isn't it better that everyone can make AI slop so the internet will be filled with AI videos and then it becomes normal which will make humanmade more valuable?"
And it's really where it says, "I believe that a lot of the videos that 3 blue on ground put out are so popular because you can tell I feel like I'm having a shout over the rain now. Let me turn this down just just a little bit."
Uh because you can tell how enthusiast enthusiastic he is about the subject. A lot of the times the enthusiasm will be felt through the metaphors and comparisons people use to explain a topic. I don't feel that AI could add the same special source to a mass related vid.
Yeah, it's it's interesting. It's an interesting time.
So, one of the reasons that in so I have a rule which is every video that I make uh it's I have I have my face in it.
like every every video I I have my face in it and partly because of the way that I went about this was I kind of saw where video where where AI was going and I think a lot of like there is a way in which you can look at things like YouTube or even Twitch and and say it's simplistically you are producing an a resource content entertainment content of some kind that you you are then delivering through a platform form to a person and it doesn't really you know doesn't really matter like uh like like how that content is produced but I think that you know particularly this comes out of out of my experience in education um like you can get correct information quite easily like correct information has been out there for a long time on most every topic you need to learn um and Now we have it in a in an easily digestible form through AI. But um a lot of education only works if you have a human relationship with another person. And there are different ways to have a human relationship like if you're a direct teacher you have a relationship with your students and likewise um it's not the same as being friends but it's still a relationship and it you know it's useful to do work with. Um, and I think I think now also like with with content the the the relationship although again it's a very different relationship than knowing people like in person it uh it makes a difference to what you're doing.
Okay. Chat is saying some interesting stuff.
Started to become distressful of videos where the narrator doesn't show their face. Yeah, me too. In a climb bottle.
It's a lot of um even where people even when people use their their voices like sometimes you can tell the script is AI generated as well.
I actually um I made an OBS plugin using AI the other day.
Um, which turned out all right. I'm not using it right now.
But, uh, yeah. Anyway, these exercises, huh? Okay. Three. Uh, let me let me let me push through these.
Use the binom. Use the binomial theorem to show that the sum Oh gosh. Okay. I just Where did I go? What did I do?
I just clicked something. Just went to a completely different place.
Okay. Right.
I clicked something.
Never click. That's the lesson. Never click if you can avoid it.
Okay. Here we are again.
Okay. Apparently, if you click that, it goes somewhere else. um use a binomial theore use the binomial theorem to show that the sum of I think that's sum of uh I don't even know that notation now the sum of all the elements ranging between k from k equals z through n maybe n choose k is 2 to the n. Does anyone know what this notation here is is is asking for? I actually don't know.
Yeah, recall. Recall would be nice. If I if I could recall it, that would that would be great. Summation. So, it's summation from K to what is the what is the K and N indicated here?
I know this is like basic basic stuff.
K= 0 to K= N. Right. Okay. Thank you.
Yeah. K= 0 to K= N.
Yeah. I didn't have it before.
Desert ambience. Okay, maybe next time.
Okay, desert ambience next time I'll I'll have a I'll have a a dry ambience next time.
Maybe uh Oh, it's hard to get dry ambience actually. Maybe like windswept lots of wind. Wow, the keying is diabolical today. just looks awful. We need to get like the Yeah. Anyway, we don't even talk We won't even talk about keying today. Keying is keying is uh Yeah, I need to change the I need I do need to change the audio track actually.
It's getting getting a little old. Tired of all this rain getting sy bring back all that horrible scraping sound we had a few weeks back.
That was rough. That was really rough.
Okay, let me write let me write this uh write this out. Okay, can you tell I've never never even written this symbol before?
It's so big. What? Okay.
Wow, this is really lagging now.
Okay. Then choose K.
Right? And this is supposed to then end up equaling 2 to the power n tall sigma.
Okay. Apparently, this is a good exercise. All right. I'm going to lock in. I'm going to lock in and try it out.
Right.
Use the binomial theorem to show this.
Now, what's the binomial theorem again?
Uh, binomial theorem. This, right? Is that the binomial theorem?
No, that's Pascal. That's That's not the binomial theorem.
Oh, why have I just forgotten what the binomial theorem is?
Terrible.
Okay.
Right. It's It's this. It's this.
That's That's what we're going to use somehow.
What?
Try writing the right hand side with the sigma summation notation.
Okay, let's try that.
So Well, let me start writing. Maybe something will come to me.
Nope. Uh, now we want to express this as a summation, do we?
in the binomial theorem. All right.
Sorry.
Okay.
Right. Okay. The right hand side with this with the summation. Okay. Well, we we have we have sums in that at least.
So, that would kind of make sense.
So we're going to then well let's try it.
So we'll have K being zero.
No wait choose K maybe.
Yeah, because then we're No, we just write we just write the sequence. Just write the sequence.
So, yeah. You know what? I'm I'm being I'm being slightly led.
So, let's say we've got like this could also be 2 + 0 in which would be.
So y is always going to be zero. for all of the terms other than right. Okay.
So if we've if if if we've got this which is the same as this then all of the terms other than the first one will end up being zero. So we end up with n0 x n.
I really thought I was going somewhere with that.
What is x? True.
Uh x is two.
True.
And then n choose zero is going to be one because there's only one. it will be the empty set.
So we get this again doesn't necessarily help us show that these two are equal though.
Everyone's reassuring me which is giving me the indication I'm on the wrong track.
Okay, these two are equivalent. This is equivalent to this.
Is there a Is there some sort of chain here? Okay. So, we've got we've got no Yeah. Okay. So, we've got these two connected.
We've got these two connected, but how does it connect to to this?
Check 94 says, "You chose 2= 2 + 0 and simplified the binomial theorem enormously.
Perhaps you can simplify it in another way.
That's true.
uh we've not touched proof proofs yet in this book. I think it's really rand.
It's probably going to This is probably um designed to create in my mind the desire to learn proofs, but we haven't we're we're in the chapter just before we get to we get to proving things in this book. Okay. So, we could have 1 + 1 to the n.
This would then get us.
We'd then be able to expand it.
But n to the one is always going to be one, right?
So, oh, I see it.
That's pleasing. Okay. So I think so the idea then is if you look at this this this here, right?
Um we're going to have n minus x to the n x nus one y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y^ 2, etc. But all of those are going to end up being one because um anything to the power sorry one to the power anything is going to be one and one to the power anything is going to be one. So we're going to end up with these these terms here all of these will end up being one.
And so we're left with this part of every term. Uh and this part goes In theory, it goes from 0 to n 0 to n, which is the range we're supposed to be calculating this within.
So that's that's the line, right? Thank you, Check 94. That that was that was uh don't think I would have gotten anywhere close to it without that. Um yeah, so this expands to basically I need to really need to get my Apple Pencil get going on this.
Uh, n0 n0 plus n one plus all the way through to uh is it is n, isn't it?
in um and then this will be what will this be?
Yeah. N minus one, right?
Yeah. N minus one plus N choose N.
which is equivalent to this thing.
All of these summed up.
Okay. Interesting.
Another one says, "What happens when where you interpret this equality about numbers of subsets of certain sizes?
something.
Um, we've seen this. We've seen this uh this loads before. This is the binary strings thing.
conditions around show proof are usually constrained to the point of eliminating any difference between those terms in most questions.
Yeah. So, it's a it's a it's a show, I suppose.
Yeah. I don't know. I this book hasn't taught me anything about proving things yet. So, it'll be surprising if it uh if it asks me to prove anything.
Okay.
Seven more things, more showing.
Probably if I did the even number questions, this would be easier.
Okay, how much do I want to work through the rest of these?
Really recommend doing 366 as well.
We've only been streaming three and a three and a/4 hours. It's not hardly time to finish yet.
Okay. Use definition 3.2 two on page 85 and fact 1.3 on page 13 to show those two things.
Right? So, we're using some different we're using some different facts. So we're showing the same thing.
Okay. So fact 3.2, we're on page 92.
Okay.
3.2. If n and k are integers, then n k n choose k denotes the number of subsets that can be made by choosing k elements from an n element set.
Yeah, my brain is in no shape for this as much as I would like it to be.
Where we going? Where are we on?
We're we're on a completely different Okay, let me return to these exercises next time. I'm just going to just going to scroll through the next one and then we'll see how I'm feeling about those exercises.
Um, where's my highlighter?
Here we go.
Okay, we'll come back to those next time.
Inclusion exclusion principle. Many counting problems involve computing the cardality of a union a union b of two finite sets.
Okay, we examine this kind of problem.
Now, first we develop a formula for A union cardality of A union B. It's tempting to say that A union B must equal Yeah, but there's not that's not right because there might be some overlap. We might do some double counting.
Uh yeah. So, right. So, therefore, the cardality of A plus the cardality of B exceeds A union B by A intersection B. That's interesting. And consequently, a cardality of a union b is equal to the cardality of a plus the cardinality of b minus the cardality of a intersection b. Interesting. I feel like I've seen that before somewhere somewhere else.
Notice that sets a b and a intersection b are all generally smaller than a union b. Generally uh so fact 3.6 has the potential of reducing the problem determining a union b to three simpler counting problems. It is called the inclusion exclusion formula because elements in a intersection b are included twice in a plus b uh then excluded. Yeah. Fine. Notice that if a intersection b is an empty set then we do in fact get this thing. This is the instance of the additional principle. Makes sense. Conversely, if a union b is equal to cardality of a plus cardality of b, then it must be a intersection b. It must be that the this is an empty set. Okay, fine. We got some examples here.
A three card hand is dealt off a off of a standard 52 card deck. How many different such hands are there for which all three cards are red or all three cards are face cards? Okay, so that's where there's going to be some intersection going on.
So, uh let me let me see if I can puzzle this one a little bit first before moving on.
How's my computer temperature doing?
One second.
Okay.
O, all of this. Let's get rid of it there.
Okay. Yeah. Anyway, what was I doing?
Um, let the Yeah. Okay. So, if we can compute the cardality of uh Three cards being red.
All three cards are red or all three cards are face cards. So that will be that's the wrong place.
That will be let's say the first one is uh R.
That's going to be uh the number of um red red hands we can produce.
That's uh 26 choose three maybe I think.
Uh and then face cards. Now how many face cards are there? There's king. Does ace count? No. King, queen, and jack. So that's three out of every 13.
Or rather, it's just four threes as 12.
So that's 12.
Oops. 12 choose 3.
Um, and then we need to somehow compute the number of all red hands that are also all face cards.
Now the red the red all red hands that can be all face cards. Now there's how many cards is that? There's um six, right?
So that'll be no that'll be six choose three.
And so we end up, you know, taking taking this adding this and subtracting this.
I think let's see whether the whether whether it adds up the same way.
Let A be the set of three card hands where all three cards are red.
Let B be the set of three card hands in which all three cards are face cards. J, a jack, king, or queen of any suit.
These sets are illustrated below.
We seek the number of three card hands that are all red or all face cards. And this number is Sorry, I messed up.
Did I mess up? No, I didn't. We see the number of Yeah. In the union. Yeah.
So then we add these and we take the intersection and we subtract that.
We examine these separately. Any hand in A is formed by selecting three cards from 26 red cards. We got that one.
Similarly, any hand in B is selected is formed by selecting three cards from the 12 face cards in the deck. So 12 choose three and that's six choose three. Okay, good.
Now we can answer our question. It's that many.
Cool. Okay.
A three card hand is dealt of a standard 52 card deck.
How many different such hands are there for which it is not the case that all three cards are red or all three cards are face cards? So, so here how many different such hands are there for which it is not the case that all three cards are red or all three cards are face cards.
So, we want to all the possible three card hands that are not all red and not all face cards.
Right? So the problem here is we end up if we end up trying to compute separately um the the number of cards the number of hands that are all red and the number of hands um that are all face cards and and then subtract those to get the number of all non- red hands and all non- red face cards and then and then add those together or something, then we're going to we're going to end up double counting because there'll be some hands which are both not red and not face cards. Interesting. Okay, we'll use the subtraction principle combined with our answer to 3.17 above. The total number of three card hands is that fine. To get our answer, we must subtract from this number the number of three card hands that are all red or all face cards. That is, we must subtract the answer from example 3.17.
Okay, fine.
This is an analog of fact 3.6 that involves three sets. Consider three sets A, B, and C as represented in the following vin diagram.
Using the same kind of reasoning that resulted in fact 3.6, six. You can convince yourself that A union B union C is the same thing as A + B + C minus A union B which is this minus sorry A intersection B which is this A intersection C which is this A intersection C sorry B intersection C which is this plus this center se section here this one. There's probably not much harm in ignoring this one for now. But if you find this kind of thing intriguing, you should definitely take a course in combinotaurics which is really Ren is I think I think saying ask your instructor.
I've got no one to ask.
Okay, I'm not going to do all those. Uh what comes after this? Multis sets and then it's division and pigeon hole principles and then it's combinatorial proof and then I think we're done with counting.
Wow, that's been pretty awkward. Okay, I think I'm going to call it a day there.
slightly shorter stream than I anticipated. But I think I can't force my brain to do anything it doesn't want to do and I don't have anything else obvious to do. I don't think so. Um I'd have to ask myself. Yeah, I would. Thanks a lot. I appreciate that.
I appreciate all of the uh all the support in chat as well.
It is uh learning is difficult.
Knowing stuff already is great. Knowing stuff's great. Learning is difficult.
But that's uh that's why um that's that it's really r you had a you had a question. You had a point about the national lottery. I there was actually an exercise earlier which asked I think exactly that.
Let me see if I can find that exercise.
I think I might have might have done it.
Maybe it was uh it was in today's stream.
No, that was last stream. It's raining again.
Or maybe it was an example.
There was something. Oh yeah. Uh but with 36 balls.
You have to write your thesis. Blah blah. Oh no. I'm sorry.
That sucks. Um, don't you could just tell us all about it, Bubbleon, if you if you like. I know people who are writing a thesis love love to talk about it, right? What's your favorite question at parties?
What's your thesis on? Um, thanks for check thanks for uh hanging out, Sam.
Um, have a good rest of your day.
Okay. Now, what's uh what are we thinking? What are we thinking raidwise now?
Who's uh who's online?
Why lazy schemer? Hi, lazy schemer. Hi.
Bye, lazy schemer.
Lot of vibe coders online. People are vibe coding, but we won't uh we'll try to avoid that.
Somebody who looks cool is streaming in Polish, but I guess it's a bit of a fauxar to just raid a Polish Polish Polish stream.
because none of you will be able to understand it unless you're Polish, in which case you will.
Is there a math category? There's a math I think there's a math tag.
Oh, wow. There is a category. That's wild. I guess I should be in that.
Whoa. I didn't even know this existed.
Wow. They're all doing it on They're all doing it on uh on paper and everything.
Wow. Okay. All right. Let's check this out. Let's check this out. All right.
We're going to we're going to go and we're going to go and raid uh we're going to go and raid somebody. Wow. This this this person's wearing a tie. That's how you know it's going to be good. All right. We got 10, nine, eight, seven, six, five, four, three, two. Have a good day everyone. Lers.
相关推荐
A Number Plus 5 Is 12
MathGirlTutor
101 views•2026-06-03
Olympiad Mathematics | Indian | Can You Solve This One?
PhilCoolMath
650 views•2026-06-03
H2 Math June Holiday 2026 Intensive Revision | H2 Math Tuition by Achevas #singaporemath #h2math
AchevasTV
304 views•2026-06-01
Escaping the Fog
LogicLemurGaming
760 views•2026-06-03
slick TMUA geometry!
JPiMaths
109 views•2026-06-04
Edexcel IAL S2 Statistics June 2025 - Complete Paper Walkthrough | WST02/01
Math_Mind_1
140 views•2026-06-03
A Brutal Radical Expression Made Easy! The Shortcut Changes Everything.
tamoshop
112 views•2026-06-02
Is This Pentomino Tileable?
3cycle
241 views•2026-05-30
