Hi everybody welcome back. In this video we're going to consider an elegant computorial structure called Pascal's Triangle. Let's start with the following well known question. I mean, we have n students and we would like to form a sport team out of them consisting of exactly k students. So what is the number of way of selecting such a team? So the answer is n choose k, well why is that? Well, this is just because we're selecting k students out of n students. So just by definition this number is equal to n choose k, okay? At the same time, let's view this number from a different viewpoint. Let's just fix some of the students, and call her Alice. Then all the possibilities are divided into two parts, naturally. First of all, there are teams with Alice. So first consider all the teams that involve Alice. I claim that the number of such teams is equal to n-1, choose k-1. Well, why is that? Because we already decided that Alice is in the team, okay? This means that we still need to select the remaining k-1 students and we need to select them from the remaining n-1 students. And this is exactly this number of ways is exactly equal to n-1 choose k-1, okay? So once again the number of teams with Alice is n-1 choose k-1. And now let's consider a lot of teams, those teams without Alice. So we already decided that Alice is not going to be in the team. This means that we actually need to select the team as a whole, okay? Students from the n-1 students, everyone except for Alice, right? And again, just by definition the number of such ways is n-1 choose k. And this gives us finally the following nice combinatorial property of the number of combinations, n choose k = n-1 choose k-1 + n-1 choose k. So once again let me try to repeat this formula. This is a number of ways of forming a team, okay, of k students, all of them students, and we represented this as naturally as two parts. So if you want to follow this is the number of ways of forming a team with some fix of student which we call Alice. And there is a number of ways of forming the team without the students. So clearly the number of ways of forming a team is equal to the sum of these two numbers, meaning this is just all the possibilities,okay? And this is an important property of this numbers. And there is an elegant way of visualizing this property. Okay, so let's try to do the following. We're going to construct the so-called Pascal triangle which will contain a separate cell for every n and k contain the value n choose k. So it is going to be constructed from top to bottom. So at the top, we have just one cell containing the value 0 choose 0. The second row corresponds to n = 1 and it has two cells, 1 choose 0 and 1 choose 1. So in general, at every row we have, it corresponds to some fixed value of n, and then it has all the values of n choose k, where k ranges from 0 to n. So when n is equal to 2, for example, k ranges from zero to 2, so we have three cells, k is equal to 0,1 or 2. When n = 3 we have four such cells, and so on. Now let's see what our equalities that we just proved means in this triangle. So let me remind you this equality n choose k = n- 1 choose k- 1 + m- 1 choose k. So essentially it means that for every element in our triangle it's very obvious equal to the sum of its two top neighboring elements. So for example, what we know is that 5 choose 2. So the value of this cell is equal to the value of this cell, plus the value of this cell. In this particular case, n = 5, that n = 5 and k = 2. So, by applying this formula, we have solved in this case, so this is 5 choose 2, n-1 choose k-1 is 4 choose 1 which is exactly this cell, right? And then -1 choose k is 4 choose 2. Okay, which is exactly this one and this holds actually for every cell, to be formal for every internal cell, right, in our table. Okay, now let me replace all these numbers with the actual values and let's take a look. So first of all, we see that at the boundaries we have the value 1 everywhere. So why is that? Well, just because of the boundaries we have numbers like n choose 0 or n choose n, so n choose 0 is always equal to 1. So it is the number of ways of selecting an empty sets, there is just one empty set. Okay n choose n is also equal to 1, well this suggest because n choose n is a number of ways of choosing a subset of size n. And there is exactly one such subset, of course. So at the boundaries, we have 1s everywhere, right? And then every other element can be computed just by computing the sums. So, for example, the 2 here can computed as the sum of 1 plus 1. 3 here can be computed as 2 plus 1. 4 here can be computed as 3 plus 1. 5 here can be computed as 1 plus 4, and so on. So 3 is computed as 1 plus 2, 6 is computed as 3 plus 3, 10 is computed as 6 plus 4 and so on. And in fact, this gives us a way computing the value of n choose ks. So if, for example, you have large numbers n and k, one way of computing n choose k is to compute n factorial then compute them divided by k factorial then divided by n-1 and n-k factorial. So it involves many multiplications and many divisions. At the same time, using Pascal's triangle, we can compute the value of n choose k just by computing some sums, as usual. So let's just declare the dictionary C such that C [[n, k] is going to be equal to n choose k, okay? Then we do the following. We loop through all the values from 0 to 7 and we do the following. First, we say that n choose 0 is always equal to 1 and n choose n is also equal to 1. In a sense what we do here, we're filling our triangle. We fill it row by row. And at every row, we first say that the values at the boundaries are equal to 1. And for every internal element in the row, we compute it as the sum of two previous elements, all right? And this is done here, so for all internal elements we apply our formula, n choose k = n- 1 choose k-1 + n- 1 choose k. Okay, so when n and k are large so it uses a lot of space for computing n choose k, but still we know that operations adjust summations. And then let's just do a sanity check. Let's print 7 choose 4. So what we expect is 7 factorial divided by 3 factorial by 4 factorial, which is 7 times 6 time 5 times 4 times 3 times 2 times 1, divided by 3 times 2 times 1. This is 3 factorial and divided by 4 times 3 times 2 times 1. This is 4 factorial. We can cancel out this immediately and then what remains is 7 times 6 times 5, divided by 3 times 2 times 1. So 6 is also canceled and what remains is 35. And the same result is printed by our recursive procedure. So once again, this Pascal's triangle gives us an informative way of computing n choose k.