We are now ready to introduce an important combinatorial object called combination. So imagine that you are going through a car journey. And you have five friends, but unfortunately you have only three vacant places in your car. So what you would like to compute is a number of ways of selecting three of your friends out of five that you are going to take with you to your journey out of five of your friends, okay? Of course, in this case we don't care who of your three friends is going to sit where in the car. So basically, what we're looking for, so speaking more formally is what is the number of ways of selecting three elements out of five elements, okay? So let's try to compute these number of ways. So you need to select three friends. There are five choices of the first friend, four choices of the second friend, and three choices of the third friend, right? So this gives us 5 x 4 x 3. But as we've seen already, this actually computes not the number of subsets of three friends, but the number of three permutations, right? In particular, each subset for example, of friends a, b, c was counted six times. It was counted as abc, for example, as acb, as bac, bca, cab and cba. But since we're not interested in the actual arrangement of these three elements, we need to divide everything by six, right? So we would like to count each subset exactly once while in our current estimate, it was counted exactly six times. So the final answer is (5 x 4 x 3) divided 3 factorial, which gives us 10. So this is an important combinatorial quantity. Let's also justify our count just by trying to generate all such combinations, namely here we have five friends, a, b,c, d, e. And we asked the combinations method to compute all possible subsets of size 3 of all these five letters. So what it gives us is exactly ten such possibilities, okay? Now, we're ready to give a definition. So if we have a set, S, then it's k-combination is a subset of size k, okay? So, and the number of different such subsets of size k is denoted by n choose k. So where n is the size of the set S. So more precisely or more formally, n choose k is defined with the number of different subsets of size k, of an n element set. And once again, it is pronounced as n choose k, and it is written like this, okay? So, this is a very important combinatorial quantity. So in particular, you can go to Google and compute any such number. For example, if you compute 5 choose 3 in Google, it will give you a result, okay? Once again, it is 10. So there are ten ways of choosing three of your friends out of five of your friends, okay? Now, before giving the formula, let's look once again at the difference between the number of 3-combinations and 3-permutations. So let's list all possible 3-permutations. So recall that in a 3-permutation, we just would like to put one of your five friends to the first place, then one of the remaining four friends to the second place, and then one of the remaining three friends to the third place. So this gives us 5 x 4 x 3 which is 60, and all 60 permutations, 3-permutations are shown here on the slide. And they are arranged in a nice way such that as you see in the same column, we have exactly the same three elements permuted, right? And we know that for elements abc, there are exactly 3 factorial possible ways of permute them, right? So in which means that the number of 3-permutations is 3 factorial larger than the number of 3-combinations. More precisely, what we see here is that in this table, the height of this table is 3 factorial while the width of this table is 5 choose 3. At the same time, the total size of the elements in this table is the number of 3-permutations. And we know how to compute it. The number of 3-permutations is 5 x 4 x 3 which is nothing else as 5 factorial divided by 2 factorial which is just 5-3 factorial. So this gives us the following formulas. The number of elements is equal to the height of this table times the width of this table, okay? And this will lead us, this substitution will lead us to the general formula for computing n choose k. So the formula is as follows. n choose k is equal to n factorial divided by k factorial, and divided by n minus k factorial, okay? So this is the formula and now let's try to prove it. So we have actually everything needed to prove it already, okay? So first, let me remind you that n choose k is the number of subsets of size k out of n elements, okay? Now, first, let's count the number of k-permutations, okay? So, for k-permutations, there are exactly n choices for the first element. Then there are n-1 choices for the second element, n-2 choices for the third element and so on. (n- k +1) choices for the k-th element. And this computes the number of k-permutations. And we know already that it is equal to n factorial divided by (n-k) factorial. Which is just a convenient way of writing the expression n times (n-1) times (n-2) times (n- k + 1), okay? And this says, as we've discussed already, this computes the number of k-permutations but not the number of k-subsets. And the number of k-permutations is exactly k factorial times larger than the number of k-subsets, right? Why is that? Well, because just when we count the number of k-permutations, every subset is counted exactly k factorial times. Because if you have a subset of size k, there are k factorial ways of permuting its elements, right? Which finally gives us the estimate n factorial divided n minus k factorial. Let me remind you that this part, n factorial divided by n minus k factorial, is exactly the number k-permutations. And we need to divide it by k factorial to finally get the number of different k subsets, okay? So once again, let me show you the results and estimate. So n choose k is equal to n factorial divided by k factorial divided by n minus k factorial.
