[SOUND] [MUSIC] Next thing we're going to discuss are k-permutations. We have seen that the permutations were corresponding to ordered lists of let's say n people. Now suppose that you're also interviewing n people for a position and finally we want to produce a short list consisting of k candidates, where k is less than or equal to n. And in how many ways can you produce a short list of k people? And In how many. Ways. Can we produce, A short list Of k candidates. Out of n. So short lists are called k permutations. And a formal definition is: A k permutation is a Total linear ordering. On a k element. Subset Of, let's say 1 to etc. N. An example. Say for n equal to 3. So if we have a set, {1,2,3} then here are all 1 permutations. So a 1 permutation is just a one element subset. So if there is only one element, there is nothing to order. So one permutation are one, two and three. And two permutations are one two, one three, two one, two three, three one, three two. So there are six of them. And again here's the theorem. And I was asked to compute the number of k permutations in the general case It is equal to n(n-1)...(n-k+1). The proof is, again, very simple. So suppose that you want form such a shortlist of length k out of n candidates, so for the 1st position in this shortlist, you have n possibilities. N possibilities for the first entry. So for the second entry in this subset you have n minus 1 possibility because the second entry can be any one out of these n except for the person who is already in the first row of your shortlist. So n minus one possibilities for the second entry. And so on and for the, kth entry there are n- k + 1 possibilities. So all these possibilities are independent, so to get the whole number, you need to take their product. And this will give you the total number, Of k permutations. And it is n times (n- 1) times etc. times (n- k + 1). Sometimes this expression is called the kth decreasing power. Sometimes you can see such a notation. Decreasing power means that you're multiplying n, n minus one, and all the subsequent numbers. And there are k factors occurring in this expression. Again, we conclude with a set theoretic interpretation. It is as follows. Suppose that, You have a k element set, x, where the cardinality of x is k. And then n element set y, Where k is less than or equal to n. In this case K permutations correspond to injective maps from k to y. Injective means that no two elements are mapped from x, are mapped to 1 element of y. So different elements of x are mapped to different elements of y. And such a situation when where two elements are mapped to the same one is forbidden. So such maps are called injective And they correspond to k permutations and element set. [MUSIC]