[MUSIC] Hello, everybody, welcome to our video lecture on discrete mathematics. A big part of discrete mathematics is actually counting all kinds of things, so all kinds of mathematical objects. And in today's lecture, I want to start with this topic which is called Enumerative Combinatorics. And we start with counting the basic mathematical objects we had to find in the last lectures like sets, functions, and so on. So as a motivating example, suppose I have to plan which dinner to cook for the next three days, Saturday, Sunday, and Monday. And let's suppose my cooking abilities are a little bit limited, and these are the five dishes I can cook. I can cook Chinese food, Mexican food, German food, pizza and pasta. So for example, something I could do, is I could say on Saturday I cooked Mexican food, on Sunday I cooked German food, and on Monday then make a pizza, okay? That's a perfectly fine thing what I could do, but I could also be lazy and say well, on Saturday I make pasta. On Sunday, I make pasta, and on Monday, I make pasta. Now that's probably a boring dinner plan but for now, this is actually allowed, so I have no restrictions, I just have to cook one dinner per evening. So another question is how many choices do we have? How many choices do I have to cook dinner for the next three days? And this is very easy so on Saturday, I have five choices, on Sunday, I have five choices, and on Monday as well. If I multiply them together I have 125 choices. All right, so what you have basically just proved is the following fact, the number of functions from the set Saturday, Sunday, Monday, into the set Mexican, German, Chinese, pizza, pasta is 5 to the 3rd, which is 125. And in general, if you have two sets, A, B the number of functions from A to B is B to the A. So here's an application of this innocent fact. So you might remember we have defined the power sets of a set, 2 to the S to be the set of all subsets. Now, we're asked the following question, how many subsets are there? So for example this is a subset, this is also a subset but the set itself is also a subset of itself, and of course, the empty set is also a subset. So how can you count the number of functions? Here is a little trick, for a subset I define 1 sub x, this is the characteristic function, it's a function from S into the set 0,1 defined as follows. 1 sub x(a) is simply 1 if a is in the set x, and it's 0 otherwise. And now you actually see that there is a one to one correspondence between characteristic functions in subsets. And therefore we see well are The number of subsets, the files of the power sets is simply the number of functions from S into 0, 1. And by what we have just proved, we see that is 2 to the size of S. All right, so here is the proof again, written up in a nice way, you can look at it in more detail if you wish. Let's continue to Part II, Counting Injective Functions. So as I have told you, there are no restrictions to cooking food for the next three days. But, of course, maybe my wife is not happy with me cooking Mexican food twice, so she actually wants that I cook three different dishes over the next three days. So this is not good. What would be good, for example, would be something like this. Just know the rule is no food twice. So basically now we are looking for an injected function. So how many choices do we have now? Well, for Saturday, I still have five choices and no matter what I chose, I have four choices left for Sunday and three choices left for Monday and together, this gives 60. In mathematical terms, it means the number of injective functions, that's actually a typo here, it's not infective, it's injective, okay. The number of injective functions from Saturday, Sunday, Monday are into my five elements set which is just 5 times 4 times 3 which is 60. And in general, if you have two finite sets, A and B, then the number of injective functions is this expression here. And this is so important that I want to introduce a notation for this. This is very useful but it's not completely standard in mathematics. So b to the a with a little line under it, is just defined to be b(b-1)(b-2)..., and you continue until you get a factors. And this is pronounced b to the falling a. All right, the big use of this notation is actually quite useful in memorative commenatories. So we have proved the number of injected functions from a to b is b to the falling a. All right, so in Part III I want to count permutations. What's a permutation? So, let's change the setup a little bit, I am planning a five course dinner for one evening. So there is one evening, and I want to cook all the food that I can cook, so there are these five choices, so I have to cook everything. But I'm not sure in which order I should serve. So for example I could say the first course is Chinese, the second is German and so on. Or I could choose a different order or this and so on. And actually as you already see there are lots of combinations I can do. There are lots of ways in which I can order these five elements. So, how many are there? So, here is the thing, the only thing I have to decide is what is the first course, the second course, the third, the fourth, the fifth. So, basically what I have to do, I have to choose an injective function from this set into the set C,G M, Pa of Pi, right? And how many other functions are there? Well, 5, to the following 5, which is 5 times 4, 3, 2, 1, which is 120. So we've proved the following theorem, these elements can be ordered in 120 different ways. And in general if you have a set of size n, then it can be ordered in that many ways. And this is also a very important formula in mathematics so we again, introduce a new notation. And we pronounce it n factorial. Okay, and if you haven't discovered it yet, I have discovered a typo. This is of course supposed to be n -2. All right, another thing to observe, the n factorial is simply the number of injective functions from s to itself. And this set of functions is injective, and it's finite, then this function must be bijective. In a bijective function from a set to itself, we also call a permutation. All right, so we are ready for the last part of today's lecture, counting subsets of a certain size. So the set up is here I'm invited to a party and I have to bring 3 dishes. So I just have to select 3 of the dishes I can cook, so for example, these here or these 3, and so on. All right, so many are there? Well one way to solve it is again to say, well I have the set 1, 2, 3, I have to select the first, the second, and the third dish to bring. So I have to find the injective function from this set into this set. For example this, So now we can say, well, the number of choices is maybe 5 to the form 3 because this is the number of functions from the left set into the right set. But now you might protest and say, well, it's not completely true because if I draw this function, it's a different function but it gives me the same set. Like this, right? It's a different function but it gives me the same set. So, every set can be obtained by a lot of functions by how many? Well, if you think about it, by three factorial many. So what is this? This is 5 times 4 times 3 divided by 3 times 2 times 1, this is 10, so I have 10 possibilities of selecting 3 dishes. So this is the following observation and in general if you have a finite set then it has this many subsets of size k. This is also very important so I want to introduce a little bit of notation. So the first thing is, S choose k. This is just the number, it's the set of subsets of S, such that x has size exactly k. And then this expression here. We pronounce it n choose k, I'll pronounce this S choose k. So we basically have proved that the size of S choose k is the size of S choose k. And this thing is very important, it has its own name, it's called a binomial coefficient. The binomial coefficient is arguably maybe the most important object in enumerative combinatorics, so we will see it a lot here in the coming section. All right, that's it for today, thank you very much and see you next time. [MUSIC]
