Another notion closely related to the notion of the word is a permutation. So as we have seen the words were anything maps from a k element set, X into an n element set Y. So this is X and this is Y and we are describing maps from x to y. And we can ask ourselves, how to count a number of maps with certain special properties. So one question, the first question of this type, is how many bijections in between x and y are there. So a bijection is a one to one correspondence. Meaning that the elements from x, meaning that no two elements from x are mapped to one element of y and every element of y appears as a prey image of a certain element of x. Well, it's clear enough that, so how to count bijections from x to y. How to count bijections, Or one to one correspondences from x to y. Well, it's clear enough that for our map to be a one to one correspondence the number of elements in these two sets should be equal. So first this means that k must be equal to n. So the cardinality of X must be equal to the cardinality of Y. >> So such a map, a bijection between x and y, is called a permutation. So definition. Permutation, Is a Bijection From the set one, two, etc, n, to itself. So we are going to compute the number of such bijections. And we can also put it in a different way. So we can index, The elements of x and the elements of y 123, 132. And in this example, we see that 1 goes to 1. 2 goes to Three, and 3. And 3 goes to 2. So we have arranged our elements of the set X in a certain order. First we put 1, then we put 3. And at the last place, we put two, so permutations equivalently, Permutations Can be considered as total layer orderings of the set 1 to n. Of So, you need to arrange them in a certain way. How many ways to do this are there? Well, it's pretty clear that the number of such ways is, Kind of found as follows. Theorem, the number of permutations. Of the set 1, 2, 3, etc, n is equal to n factorial, which is one times two times three times etc times n. Okay so again total linear orderings are ways to arrange these elements in a certain order in such way that you can't compare any two of them. So suppose that, you want to hire some people to a company, and you have n candidates and you have interviewed all of them and so at the end, you can produce arranged list and ordered list of candidates. Well the best one on the first place, the second one following him or her, and so on and so on. So the number of such lists is equal to n factorial. Why is it so? Proof that the first entry can go to any elements of the set Y namely from any number from 1 to n. So, on the first position you can have any one out of the n candidates. So, for the 1st element you have n choices. For the 1st element There are n choices. So what about the 2nd element? The 2nd element can go to any number different from the number 1 went to. So, well in this example, 2 can go either to 2 or to 3 but not to 1 because 1 is already taken by the first entry. So for the second element there are n-1 choices. Etc. So for kth element And there will be n-k+1 choices. And etc. And for the last one There will be just one choice. Because the last entry, for the last entry you have no freedom. It goes to the only position not occupied by the previous other ones. So the total number is n (n-1) (n-2)..times etc 2.1 amd this is n! So, a word of warning or a convention, Later on in this lecture and in our following lectures we will use factorials a lot, but let's say that zero factorial is 1. So if you have no candidates at all. You can arrange this entries in just one way. So the number of ways to arrange this list is 1 not 0. So this conventional will be used loater today and in the following lectures. So we have computed the number of permutations of n element set and now we will generalize this to injective maps from X to Y, where X and Y have maybe different cardinalities.