Next thing we are going to discuss are binomial coefficients and enumeration of subsets. Definition: suppose we have two integers, k and n, and let k be less than or equal to n. Then the number of k-element subsets of the set of n elements is called a binomial coefficient. n choose k. So this is written as follows: n upstairs and k downstairs in brackets, and it is read "n choose k". First you read n which is upstairs and then k downstairs. So what can be an interpretation of this number? So suppose again that you're hiring people to certain positions and suppose that you have n candidates, and you have k identical positions. So now you're not forming any ranged lists anymore, you just say to k candidates that they are taken, that they got this position. So the number of selecting k people out of n is called n choose k. So, the theorem, how to compute this number, which is probably familiar to you. n choose k is computed as n factorial divided by k factorial times n - k factorial. Or if you divide the numerator and denominator by n - k factorial, you get n times n - 1, etc, n - k + 1 in the numerator, and k factorial in the denominator. Note that upstairs and downstairs you have k factors. And upstairs you have the kth decreasing power of n, something that we have seen when we were discussing k-permutations, and this is, of course, not a coincidence. Proof. How to show this, how to show that n choose k, the number of k-element subsets, is indeed given by this formula. Well, we can say that, first, you can take, if you want to hire k people, then you can take an ordered least of these k people, and then forget about the order. So, take a k-permutation and forget about the order. So, the number of ways of taking k-permutation is the numerator of this fraction, so there are n times n - 1 times etc times n - k + 1, k-permutations. And these k entries in this list can be ordered in k factorial ways. So k factorial orderings give us the same subset. Because you are not interested in the order of these k elements any more. So you only care about the entries occurring in this list. So you need to divide this number by this, and what you get is the number of k-element subsets. By the way, it is not so easy to prove directly that this number is integer, that the set of k consecutive integers is always divisible by k. But here is a combinatorial proof of this fact, because, well, this number is integer because it is the number of k-element subsets in an n-element set. Okay, and so these are the binomial coefficients. We will see in a couple of minutes why are they called so. And now, we are going to list some of their properties. So these numbers occur in many many combinatorial problems, and they will be in great importance for us. So let us list some of their properties. First, some of the properties follow exactly from the definition. What about the extreme cases? What about, say 0-element subsets or n-element subsets of an n-element set. Well, there is only one of each of those subsets, there is an empty set in this case and there is the whole set 1 to n in this case, so this number is equal to 1. Then what about n choose 1? You see that there is only n possibilities of picking one element out of n. And same about n choose n - 1. If you want to pick n - 1 element, that means that you do not choose, you leave only one element. So this number is equal to this one, and it is equal to n. Then, well, these two properties suggest us that there should be some kind of symmetry, and indeed there is such a symmetry, n choose k turns out to be equal to n choose n - k. Okay, here is a proof of this fact. If you want to take a k-element subset of an n-element set 1 to n, and this means that you need to leave out n - k elements. So taking a subset means not taking its complement. And its complement consists of n - k entries. So, here is a combinatorial proof of this identity. And, of course, there is, to prove it, you can also use this theorem, the exact formula, and you can note that this expression is clearly symmetric in k and n - k, but, indeed, to show this identity, you do not need the exact expression, you can use some combinatorial reasoning. And, well, this will be a general phenomenon that some of the identities have several proofs, some of them have both algebraic and combinatorial proofs. And whenever it's possible we'll mostly use combinatorial proofs, as sometimes they're more interesting and provide deeper insight. Okay. What about other properties of binomial coefficients? So, another property is that there is a recurrence relation on the binomial coefficients. It says that n choose k is equal to n choose n - 1 choose k - 1 plus n - 1 choose k. Here is a proof of this fact, well, first proof is, the first proof is algebraic. And to carry out this proof you need to write down the left-hand side and the right-hand side using this formula, and check that this is indeed an identity. This is not that interesting, and if you wish you can do it yourselves as an exercise. And what is more interesting is a combinatorial proof of this fact. Now let us pick an element of this set, let's say, 1. All your subsets, k-element subsets, are divided into two parts, some of them contain 1, and the others do not. Containing 1 and not containing 1. So in how many ways can we pick a subset containing 1 consisting of k elements? Okay, so we have already picked the element 1 as one of the elements of our subset. This means that we need to pick k - 1 elements out of the remaining ones, out of n - 1. So, there are n - 1 choose k - 1 subsets containing 1. What about those? I claim that if our k-element subset of this set 1 etc n does not contain 1, it is the same as a k-element subset of an n - 1 element set, 2, 3, etc, n. So there are n - 1 choose k possibilities to pick, to pick a subset of not containing 1, because 1 is a forbidden element, we are not taking it. So the set of k-element subsets is split into two parts, and in the first part there are that many subsets: n - k choose k - 1, and in the second part there are n - 1 choose k, and they add up to the number of k-element subsets, which is exactly n choose k. So this identity is proven.