0:00

Now let's apply what we've just learned to solve several problems.

Â So the first problem is actually easy.

Â So the question is what is the number of ways of selecting 5-cards

Â out of 52-cards out of a standard deck consisting of 52-cards.

Â So one such combination is shown here on the slide.

Â And the question is, of course, it is just 52, choose 5,

Â which is roughly 2.5 million, okay?

Â Now let's slightly change the problem.

Â Now we are looking for a number of ways of selecting five cards,

Â such that two of them are hearts and three of them are spades.

Â Now we see that we can arrange our five cards as follows,

Â such that first we have two hearts and then we have three spades, okay?

Â Then to count such number of ways, we actually need to realize that,

Â for each of the first two cards, their are thirteen possibilities.

Â All 13 hearts cards, right?

Â And among these certain cards, we need to select two.

Â And the same for spades, we need to select three spades from thirteen possibilities.

Â So by the product rule, the answer is 13 choose 2,

Â and times 13 choose 3, which is roughly 22,000, okay?

Â So the next problem is about numbers.

Â In this case, we are interested in non-negative

Â integers with at most four digits,

Â such that at least one of the digits is equal to seven.

Â So in this case, it turns out that it is easier to

Â compute the complement of what we need to compute.

Â Namely, let's compute the number of non-negative

Â integers with at most four digits that do not contain seven as a digit, okay?

Â It is not difficult to compute.

Â So for any, so there are four digits.

Â And for each of four possibilities, we have just nine choices.

Â All the ten digits except for seven,

Â which means that there are 9 to the 4 such possibilities.

Â And the total number of at most four digit numbers is 10 to the 4.

Â Which means that we need to subtract 9 to the 4 from 10 to the 4,

Â which gives us something like 3,000 and roughly a half.

Â And we can double-check this using a simple for loop in Python, like this.

Â So let's just consider all possible tuples of four digits.

Â And for each such tuple, we check whether seven is present in this tuple or not.

Â If yes, we just increase our resulting count by one.

Â So in the end, we print count and

Â to double-check we print also the value of 10 to 4- 9 to the 4.

Â So as we see, it is exactly the same number.

Â So the next one is the following also typical problem.

Â We would like to compute the number of

Â non-negative integers with at most four digits,

Â such that the digits are strictly increasing.

Â So this is probably a slightly more complicated example.

Â So this case, we need to realize that first all the four

Â digits in our number are actually different, okay?

Â But this in turn means that our goal is just to select

Â four different digits out of ten possible digits.

Â And then what we need to do is to arrange them in increasing order, right?

Â But this in turn means that the answer is [INAUDIBLE]

Â 10 choose 4, which is equal to 210.

Â Once again, let's double-check this, let's implement the following simple procedure.

Â So we'd just ranges through all possible tuples of four digits.

Â So this is through [INAUDIBLE] all the possibilities of digits from nine to ten.

Â Then, if the zero digit is smaller than the first one, the first one

Â is smaller than the second one, and the second one is smaller than the third one,

Â meaning that the digits are indeed increasing, then we increase the count.

Â And also we print the resulting number.

Â In the end, we print the count, okay?

Â So, then, if we run this program, we will start printing numbers like 0, 1, 2, 3.

Â Any of this digits is numbers, then 0, 1, through 4 and so on.

Â So something is missing here in the middle of this list.

Â And then the end of this list looks as follows.

Â 6, 7, 8, 9, which is kind of the largest four digit number with increasing digit.

Â And then, we also create a column which is indeed 210, which is nothing else.

Â Once again is 10 choose 4, okay?

Â Finally, let's revisit the following problem.

Â So we are given a board, for example, an eight by eight chessboard.

Â And we have a piece whose initial position is at the cell [0,0].

Â And what we would like to do is to count the number of ways to get, for

Â example, to the cell [5,3],

Â to the cell whose row is fifth one and who's column is the third one.

Â So we would like to count this number of ways assuming that,

Â in a single move, this piece moves either to the right or moves up, okay?

Â So first of all, it is clear that the number of moves should be exactly eight.

Â In any possible movement from this position to that position,

Â the piece should make exactly eight moves.

Â Why is that?

Â Well, just because each time we either increase the row number or

Â we increase the column number.

Â Initially, the row number and the column number is equal to 0.

Â In the end, the row number is equal to 5 and the column number is equal to 3.

Â So with each move the sum is increased by exactly one.

Â Initially it is zero.

Â In the end, it is 8, so the number of moves must be equal to 8.

Â And this gives us a hint, so we need to make 8 moves.

Â On the other hand, we know for

Â sure that the number of moves to the right should be exactly 3.

Â If we make less than 3 moves to the right,

Â then we will not be able to reach the third column.

Â If we make more than 3 moves to the right,

Â then we will not be able to return back to the third column.

Â 7:35

This is on one hand, okay?

Â On the other hand, if you can see that any such combination of eight moves

Â such that among these eight moves there are exactly three moves to the right,

Â then we reach the position [5, 3].

Â Well, why is that?

Â Just because if there are exactly three moves to the right,

Â this means that after this, we are at the third column for sure.

Â And since there are exactly three moves to the right,

Â all the other moves are going up, okay?

Â And this, in fact, means that we are not in the fifths hole.

Â So exactly in our final position.

Â And this now allows us to conclude that the number of such possibilities is

Â 8 choose 3, which is nothing else as 56.

Â It is also interesting to note that we could also compute this number as

Â the number of ways of selecting moves up.

Â 5 moves up among 8 possible moves.

Â This will give us another solution, which is 8 choose 5, okay?

Â So this is the same as selecting 5 moves up among all 8 moves.

Â But at the same time, 8 choose 5 is equal to 8 choose 3, as we know already, right?

Â This is a property of these binomial coefficients.

Â Finally, let me also show you that the same result can

Â be achieved by drawing an analogy through the Pascal's Triangle.

Â So now let's do the following.

Â For every cell in our board,

Â we going to compute the number of ways of getting to this cell.

Â First of all, for some numbers, it is easy, okay?

Â So we know that for all these cells, it is equal to 1.

Â And for all these cells, it is also equal to 1.

Â For example, for this cell, the only possible

Â way to get there is to go to the right, okay?

Â Now let's do the following.

Â Let's start computing this number for all other cells.

Â 2 for example, we show two here.

Â Why is 2?

Â Well, this is just because for every cell in our board, there are two

Â possibilities of the previous move before it gets into these cells.

Â So we might go over there from this cell or from this cell, okay?

Â And in fact, it is not difficult to see that we go either this way or

Â we go either this way.

Â In this case, it is easy to see, it is equal to 2.

Â But also, this is true in general.

Â If we have some particular cell here, for example,

Â then any correct way of getting to this cell,

Â either its last move is either from this neighbor from the left or

Â the neighbor from below, okay?

Â Which basically means that if we have a number of ways here which is equal to a,

Â and the number of ways here which is equal to b,

Â then the number of ways which we need to compute here is a + b.

Â So the numbers that we compute satisfies this nice properties.

Â In every cell, the value is equal to the value of

Â its neighbor to the left and the value of its neighbor below, okay?

Â And this allows us to fill in this table as follows.

Â So here we have 3 just because it is the sum of 2 and 1, okay?

Â Now let's continue filling in this table.

Â So this 3 is equal to 1 + 2.

Â 11:20

Finally, this 4 is equal to the sum of 1 + 3.

Â Well, not finally, I'm sorry, but

Â I'm still going to fill in this table, so this 6 = 3 + 3, and so on.

Â This 4 = 1 + 3.

Â Now, let me continue doing this by hand.

Â So here we put 5 because it is 4 + 1.

Â Here we put 10 because it is 4+ 6.

Â Here we put 10 because it is 4 + 6 and here we put 5.

Â Then here we put 15, here we put 20,

Â 15 and then also 6.

Â Here we put 35, here we put 21, and

Â finally, here we get 56 exactly.

Â So for this cell that we were interested in, we get exactly the same result.

Â And you've probably already noticed that what were doing is actually filling

Â in the Pascal Triangle whose products was actually to be here.

Â So this is like the zero's row of Pascal's Triangle.

Â This is the first row of Pascal Triangle.

Â This is zero.

Â This is first.

Â This is second one.

Â This is third one.

Â This is fourth one.

Â This is fifth one and so on.

Â So this cell, 5, 3, actually lies

Â on the eighth row of Pascal's Triangle.

Â We basically know that at eighth row what all the values are of

Â the form 8 choose something.

Â So this particular cell is 8 choose 5.

Â So this is another proof of the fact that to get to the cell 5,

Â 3, the number of ways to do this is 8 choose 5.

Â