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.