Hi. I am Vladimir Podolskii, and in this lesson we are going to discuss binomial coefficients extensively. Let's start with the following problem: suppose we have a dataset of size n to train our Machine Learning model. In some settings, we need to separate a testing dataset from our dataset to use in the following way. We will use the remaining data to actually train our model, and we will use a testing dataset to check how effective our model actually is. So we want to separate the testing data set of size k. How many ways do you have to do it? So what do we want to do? We want to pick a subset of size k of our n element set. We started with this in the previous week. We actually know the answer. The answer is n choose k and here is a formula. But now, let's look at this problem from a different angle. Let's consider one element A in our dataset. Now, we can see that there are two types of testing datasets. There are testing datasets that contain A, and there are testing datasets that doesn't contain A. Okay. Let's consider them separately. We actually know how many testing datasets do we have of both types. For the first type there are n minus 1 choose k minus 1 testing datasets. So why is this so? If the dataset contains A, then it remains for us to pick k minus 1 elements in the remaining A minus 1 set. Okay. For the second type, there are n minus 1 choose k testing sets. Why is this so? If the dataset doesn't contain A, then it remains for us to pick k elements in A n minus 1 element set. Okay. So by the rule of thumb, we have n minus 1 choose k minus 1 plus n minus 1 choose k testing sets in total. Okay. Now, in our problem, on one hand the answer is n choose k. On the other hand, the answer is n minus 1 choose k minus 1 plus n minus 1 choose k. Okay. What does this mean? This means that we have the following relation between binomial coefficients. We actually can check the same relation by the direct calculation. Okay. n choose k is equal to n factorial divided by k factorial times n minus k factorial. We have similar expressions for n minus 1 choose k minus 1 and n minus 1 choose k. So let's consider their sum. Let's move out to the brackets. All multipliers we can move out of the brackets. Then from the first fraction, we will have 1 divide by n minus k in the brackets, and from the second, one over k. Let's sum them up. It is easy to see that the result is n factorial divided by k factorial times n minus k factorial. With this relation in hand, we're ready to discuss Pascal's Triangle; a convenient way to represent binomial coefficients. In the top of a triangle, let's write the binomial coefficient, zero choose zero. Then on the next level, let's write binomial coefficients one choose zero and one choose one. In the next line, let's write binomial coefficients for n equals 2, then for n equals 3, for n equals 4 and for n equals 5 and so on. Okay. So why is this a convenient way to represent binomial coefficients? Let's recall our relation. We can see now that this relation allows us to compute each binomial coefficient from the two coefficients above it. We have that five choose two is equal to four choose one plus four choose two. So each binomial coefficient here is equal to the sum of two binomial coefficients above it. Let's substitute binomial coefficients by actual numbers here. We can see that this relation is true for each binomial coefficient on the picture. It is equal to the sum of two binomial coefficients above. This relation can actually be used to compute binomial coefficients. Let's consider the corresponding Python code. In the first line of the code, we introduce a data structure to store our binomial coefficients. Then for all n starting from zero to seven, we run the following cycle. We first set n choose and n choose n to be equal to one. Then for n choose k for all k between zero and n, we use our formula. This allows us to compute binomial coefficients from the binomial coefficients for smaller n. Let's print seven choose four and the output will be 35. So this formula allows us to compute binomial coefficients. So what ways do we have to compute binomial coefficients? We know that n choose k is equal to n factorial divided by k factorial multiplied by n minus k factorial. This can actually be used to compute binomial coefficients, but this is not a very good way. The numbers here can become large. There are a lot of multiplications here so this is not very good option. Now, what option do you have? Now is to use this formula: n choose k is equal to n minus 1 choose k minus 1 plus n minus 1 choose k. We can actually do it. This is actually much better. Another good option, is to use the following: n choose k is equal to n divided by k times n minus 1 choose k minus 1. It is not hard to check this formula and it can also be used to compute binomial coefficients. Okay. Now, let's proceed to some other properties of binomial coefficients. Let's consider a Pascal triangle again. Let's observe that it is actually symmetrical. If we draw a vertical line through the middle of the triangle, let's note that a number's on both sides of the line are symmetrical. We can write this as the following formula: n choose k is equal to n choose n minus k. So we have the following theorem. Let's provide the proof of this theorem by direct calculation. So we have it. n choose k is equal to n factorial divided by k factorial multiplied by n minus k factorial and actually the exactly same expression we have for n choose n minus k. Okay. Now, let's observe one more important property of binomial coefficients. Let's note that if k is at most n over two, then n choose k minus one is less than n choose k. We can again, prove this by direct calculation. Indeed, if we just write down n choose k minus 1. This is n factorial divided by k minus 1 factorial multiplied by n minus k plus 1 factorial. This is equal to k divided by n minus k plus 1 multiplied by n factorial divided by k factorial multiplied by n minus k factorial. The latter part is equal to n choose k and the whole expression is less than n choose k, and the last inequality follows since k divided by n minus k plus 1 is less than one. Why is this so? Observe it if k is at most n over two, then n minus k is at least n over two. Then n minus k plus 1 is greater than n over two. So the numerator here is at most n over two and the denominator is greater than n over two. So the whole expression is less than one. Okay. Now, by symmetry we can actually also observe, that if k is at least n over two, then n choose k is greater than n choose k plus 1. Okay. Let's see what it means in terms of Pascal's triangle. What it means in the picture. These two results; these two inequalities means that binomial coefficients grow in the middle. If you go from left to right, then they first grow up to the middle of the triangle and then they start to decrease.