[MUSIC] Let us start. This is lecture one, it is entitled permutations and binomial coefficients. And we'll start by defining words. Words in the meaning not in the ordinary one. So here's the definition. Let capital A be a finite set. A stands for the alphabet. A word is a finite sequence of entries of this set A. So these elements are allowed to repeat, occur more than once. For example, If our A is, 1, 2, 3, 4, the following are examples of words, let's say of length three. 112, or 333, or 142, or 232, and so on. Okay, how to count the number of words in a given alphabet. This is a very easy problem, but it will be very useful for us later. Theorem. The number of words, Of length k in an alphabet with of cardinality n. In an alphabet consisting of n letters. Equals, n to the power k. And the proof is very simple. Suppose we want to construct a word of length k in n letters. For the first letter there are n possibilities, the first letter can be an arbitrary character from our alphabet A. For the first letter, There are n possibilities. The same holds for the second letter to the second place, you can put any out of the n letters of our alphabet. And so on and so on. Same for all other letters. So the total number of words equals, n times n times etc times n k times. Because we have k positions, for letters and this is nothing but n to the power k. The proof is finished. Okay, another interpretation of this problem is that words enumerate maps from a k element set to an n element set. So, Let, Let x be a k element set. Let's say 1, 2, etc k. y be a set 1, 2, etc, n. Then the words enumerate maps from x to y without any additional conditions. So a map from x to y is a corresponding sending each element of x into a certain element of the set y. And there are no supplementary conditions on this. Namely some elements from x can be sent to one element from y. There can be elements in y not appearing in the image of this map. So the number of search maps, is, also nothing but n to the power k. So the number of maps from x to y is n to the power k. How to prove this? Indeed, we can enumerate the elements of x and the elements of y. So these are 1, 2, 3, 4, 5. And these say, 1, 2, 3, 4, 5. And, let's put let's say 6 here. To have different numbers of entries in x and y. And, Each map from x to y corresponds to a word in n letters, where n is the cardinality of y. Indeed, the first letter of our word f corresponds to the word where the first letter of this word is f(1), so the image of the element one, f(2) etc f(k). So this is a word of length k. In n letters where n is the cardinality of y. And the number of such words is n to the power k by this theorem. [MUSIC]