[MUSIC] Now we'll apply the inclusion and exclusion principle to the so called derangement problem. But before that, let me make just one remark to the inclusion and exclusion principle. Sometimes it turns out that the problem we're considering is symmetric in the following sense that, If we have the sets A1, etc., An, then the number of elements in each intersection of k sets, Ai intersected with Ai1 intersected with Ai2, etc. Aik does not depend, On the Ai's, But only on k. This means that each intersection of k sets has the same number of element, elements depending only upon k. In particular, all the sets, A1 etc., An, consists of the same number of n's. And we note this number by A to the power of k. It is by definition the number of elements in each of these. Then, the inclusion-exclusion formula can be written in the following form. Then the number of elements in the union, Is n times A, which means that we take the sum, the cardinalities, of all Ai's minus the double intersections, which all consist of the same number of elements. And there are n choose 2 of them, plus n choose 3. A cubed minus, minus etc., plus negative 1 to the power A minus 1, A to the power n. And this is this symmetric variant of the inclusion exclusion formula. And now, let us apply this formula to the derangement problem. The problem is as follows. Suppose we have and people who come to a theater and each of them leaves their coat in the cloak room before the play and after the play ends, everyone gets a coat back. But let's say that the attendant does not look at the tickets. So he gives to each person some random coat which may not belong to him, but which may belong to someone else. So n people leave their coats, In the cloak room. And afterwards each of them gets a random coat. Gets, Back a random coat, Which may belong to him or to someone else. And what is the probability that everyone will get someone else's coat? Well sometimes this problem is formulated with, N letters which are sent by secretary and they are put into envelopes but the secretary puts each letter into random envelopes, and what's the probability that everyone will get a letter addressed to someone else? Okay, so the total number of configurations of permutations is, as we know, n factorial. N factorial is the total number, Of permutations. Well, configurations of coats. And our question is, in how many ways does this permutation map each number into a different number? So, how many permutations out of these have no fixed points? That is, That they never map a number into itself. Well to compute those, we're going to compute the opposite number, namely the number of permutations having at least one fixed point or the number of situations where someone will get his or her own coat back. So, we compute the number, Of permutations with fixed points. And let Ai denote the set of permutations bringing i to itself. And while in similar way, if we take any subset of numbers from 1 to n, Ai1 intersected with Aik is the set of permutations bringing I1 into I1 etc., Ik into Ik. And what we want to get, we're interested in the number n factorial minus A1 union with A2 union with An. And how to compute this number? Well first we, let's look at each individual AI. The number of elements inside each AI, Actually it does not depend upon I. So where in this situation, and this means that this permutation brings i to i. And for all the remaining n minus 1 variable, there are no restrictions. So there are n minus 1 factorial possibilities. And let us look at intersections of k, and this means that a permutation from this set brings i1 into i1, etc., ik into ik. So for k entries, their position is fixed. And the remaining n minus k entries can be mapped either to any other entries different from i1 etc., ik. So, Ai1 intersecting with Aik. Undenoted by A to the power of K and this is n minus K factorial. Okay, then let us apply this version of the inclusion, exclusion principle. So then the unit, This is the set of permutations having fixed points, A1 union with A2 union with An is n times, n minus 1 factorial, minus n choose 2, times n minus 2 factorial plus etc., plus negative 1 to the power of n minus one, times 0 factorial. So we see that this is n factorial. This is n times n minus 1 over 2 times n minus 2 factorial. So this is n factorial, Divided by 2 factorial. Plus, again in the numerator, we get n factorial. And in the denominator we get 3 factorial. Minus etc., plus. Negative 1 to the power n minus 1, n factorial divided by n factorial. And the total number of configurations is n factorial minus this sum. And let me write it as follows. n factorial minus A1, etc, An. Such permutations are called derangements. Is n factorial times 1 minus 1 plus 1 over 2 factorial minus 1 over 3 factorial plus etc., plus minus 1 to the power n divided by n factorial. And, This is the number of derangements, the number of configurations, such that each person does get someone else's coat. And if you want to find the probability, you need to divide it by the total number of configurations, namely by n factorial. So, let me write down this probability. So, we have found the number of derangements. And the probability is obtained as, well let me denote it by p of n as a function of n. It is obtained as the total number of derangements, here it is, divided by the total number of configurations, n factorial. So, this is 1 minus 1 plus 1 over 2 factorial minus 1 over 3 factorial plus etc., plus negative 1 to the power n divided by n factorial. And while this formula allows you to compute this probability for an arbitrary n, but it is instructive to look at the limit of this value as n tends to infinity. So you probably remember the series for the exponential. So e to the power x can be found as 1 plus x plus x squared over 2 factorial plus x cubed divided by 3 factorial plus etc., up to infinity. Let me put here x to the power n divided by n factorial plus etc. So as n tends to infinity. This series gives you exactly the exponential of negative 1. So, The limit of P of n, as n tends to infinity, is 1 minus 1 plus 1 over 2 factorial minus 1 over 3 factorial plus etc., up to infinity. And this is e to the power minus 1 which is 1 over e where e is the base of natural logarithms. So where, Where e is the base of natural logarithms, it's 2., 71828, etc. And so 1 over e equals approximately 0.37 so and in fact this probability converges to 1 over e pretty rapidly. So if there are, say ten people come into a theatre, the probability that everyone will get someone else's coat is pretty close to this value, so a little bit more than one third. And this problem is, As I said, an amazing example where the combinatorial problem where problem completed from combinatorics, gives you such a value as e as the base of natural logarithms. Something that as we usually think belongs to analysis, belongs to a completely different branch of mathematics. But here we get it in a combinatorial problem. So this problem as we have put it, shows the unity of different branches of mathematics. This is all for today, thank you. [MUSIC]
