[MUSIC] Hello, and welcome back to Introduction to Enumerative Combinatorics. This is lecture two. It is entitled binomial coefficient Part 2. And principle of inclusion and exclusion. Abbreviated as pi. We'll start with this cause in certain problems where my normal coefficients appear. We already dealt with them in our previous lecture, we discussed a couple of identities, featuring binomial coefficients. Let's see how they appear in some other commentary problems. The first power we are going to discuss is the cab driver problem. Supposedly, we have a city with a regular grid of streets and avenues, like Manhattan. And let's say that from north to south this city contains of let's say n blocks. And from west to east they consist of m blocks. Suppose that after we have our taxi driver, who wants to drive from this point to that one, from A to B. And, of course, he will be only driving neither north or east. S,o his typical way will look like something like this. So, he can drive let's say one block north, two blocks east, another block north. Let's say three blocks east two blocks north, one block east, and finally one block north, and we're here at the point B, at our destination point. The question is, in how many ways can this cab arrive from the point A to the point B? Of course, there are multiple ways to do this. Well, for instance he can drive all the way north and then all the way east. or In some way like, like the one which is depicted here. So the question is, in how many ways can we get from point A to point B? Of course we are only allowed to go east or north and we're not allowed to go backwards. Okay, there are certain ways of solving this problem. First, before I show the solution, let's try to guess how to approach it. As usual, we started with some particular cases. For which this problem is especially simple. Example. Say if the city consists of only one block in the north, south, direction. So if n=1, then We have m blocks here, so yeah, we can denote this number by, let's say by Pm,n. And then number of, Such paths, Going from A to B. Okay, so if our city looks like this, then we can get from A to B in n + 1 way. For instance, we can go first north and then all the way east. Or we can go one block east, one block north, and then all the way east, etc. So, we at some point, we need to take an avenue. There are n + 1 possible ways of doing this. There are m plus one avenues, separating m blocks. So, Pm1 + to m+1. Or we can do an even more trivial example. Let's look at our city consisting of only of one street. This corresponds to n = 0, and in this case, there is only one way from A to B, so Pm,0 = 1. Okay, let's do a less real example, m = n = 2. In this case we're inside a 2 by 2 square. And you can easily count that there are six possible ways of arriving from this point to this one. Namely, we can go either first north then east. Or we can go North, East, North, East, or North to last East. One block north or one block east, north, north, east. Or make a zig zag like this. Or go first two blocks east and then two blocks north, and we get six. So, P 2,2 = 6. We have it listed all such ways. Okay, so, how to find Pm,n for and for arbitrary values of n and m. Well, there are certain ways to do this. One of the possible ways is to establish a recurrence relation. So, in solution one, Establish a recurrence relation on Pm,n Namely, let's look at the first block our way from A to B. So, on the first step the driver is The driver can go either north or east, suppose he drove the first block north, and he gets to this point. This means that once he's here and he wants to go to B. Lets call this point A prime. He needs to go from A prime to B, and this can be done in In how many ways? It's the number of paths in our tangle of times m time n- 1. Let's say P from A to B is equal to the number paths from A prime to B. Plus the number bats corresponding to the horizontal angle at the first tip. So, let's call this point A two primes. So, the number of paths from A to B is equal to the number of paths from A prime to B, or plus the number of paths from A to primes to B. So, at the first step, after the first step, he gets either here or there. And if his at a point, A two primes the remaining path is in the rectangle of size (m- 1) times n. So we can see that, Pm,n = Pm,n -1 + Pm- 1n. And we're going to see that this recurrence relation is very similar to the recurrence relation on the binomial coefficient, which I would have seen in our previous lecture. And we have the boundary conditions, the initial conditions, saying that P n zero is 1. Or in a similar way, P0n is also 1. And we see that Pm1 is m+1 and P1, n is n+1. So, in this way we can figure that the numbers Pm,n satisfy the same recurrence relation as the binomial coefficients and the same initial conditions., And we see that Pmn is nothing but the number of ways of Picking nm or n elements subset and then m + n elements set, always is the same. M+n choose n. Okay, Why is it so? Because these numbers satisfy the same recursive relation as these. Okay, and there is One more. Well, this was the first edition of this problem. And there is one more way of understanding why the number of ways is exactly m +n choose m. This means that these ways and code, subsets consisting of. And elements inside a certain m plus n elements step. What is this step and what are these half-steps and how are they related to paths? Well, the answer is given by a solution to which does not involve any recurrence relations, and it is as follows. Suppose that we have a path from A to B. It can be encoded by An instruction to the cab driver of saying where he must go north, and where he must go east. So, the paths from A to B correspond to sequences. Of the following form of letters N and E. N's and E's standing for north and east respectively. And of length m + n m+n. Saying that to go from A to B the driver should drive n + n blocks in total. And out of these n plus n blocks he would drive exactly n blocks north. Or, what is the same exactly m blocks east. With exactly n Capital N's and m capital E's. For instance, this pink path from A to B, we can put into correspondence the following instruction. Saying that, okay, you're going this way, so you're going first one block north, then two blocks east, then one block north, three blocks east, then two Ns One E and one N. So, in total we have, m+n letter here, and out of the m+n letters we need to select those which correspond to block thier north, so we need to pick 10 of them, corresponding to ns. One, two, three, four, five in this example. And this can be done exactly in m+n choose m ways. Because we have m + n positions, and we need to select n letters out of this m + n. Okay, so we have constructed a bijection between these paths and these sequences, and the number of these sequences with satisfying this condition is exactly n + n choose m. So, we have solved this problem in a different way. [SOUND]