Skip main navigation

Derangements

Derangements
10.5
Let’s see here some applications of the Inclusion-Exclusion Principle. Consider, for instance, the problem called the hat problem. n persons go to the restaurant, and each of them leaves his own hat at the check-room. And in how many ways can the n hats be redistributed in such a way that nobody receives his own hat? Let us formulate it in a mathematical way. We first label the clients and the hat with numbers from 1 to n. And we describe the outcome of the distribution of hats as n-sequence x1, xn, where x1 will be the number of the hat given to person number 1; x2, the hat given to person number 2; xn, the hat given to person number n.
71.1
So it will be a permutation of the sequence 1, 2, 3, n. And nobody will receive his own hat if and only if xi is different from i for every i. Such a sequence is called the derangement of 1, 2, 3, n. Let us count the number of these the derangements. We first give a precise definition of derangement. A derangement of an n-sequence b1, bn of a set of numbers Ik– so 1, 2, 3, k– is any permutation a1, an of the original sequence in such a way that for each i, at every position, ai’s different from bi. So at any place, the number that appears is different from the original one.
127.4
For example, the sequence 3, 1, 2 is a derangement of 1, 2, 3, because 1 is different from 3, 2 is different from 1, and 3 is different from 2. Instead, 3, 2, 1 is not a derangement of 1, 2, 3, because 2 remains at its place.
147.8
We want to count the number of derangements of the sequence 1, 2, 3, n, which has distinct elements. And this number turns out to be– we will denote by Dn– factorial of n, times 1 minus 1 over factorial of 1, plus 1 over factorial of 2, and so on. Notice that the term between the brackets are the first n plus 1 terms of the Taylor development of e to minus 1.
187.5
So how to compute the n? Well, let us consider the set X of all the permutations of 1n. Among this permutation, we want to compute the number of derangements– so the sequences that do not keep 1 at its place, do not keep 2 its place, do not keep n at its place. So let us consider the sets Ai of all the permutations of 1n in which i remains at position i for i going from 1 to n.
222.5
And what we want is the number of elements of sequences that do not keep 1 at its position– so the complement of A1 intersection the sequences that do not keep 2 at its positions, so the complement of A2, and so on, up to the complement of An. So it is the perfect setting to apply the Inclusion-Exclusion Principle in the intersection 4. Let us apply it. Well, we have to compute the number of elements of X, that is, the permutations of 1n, which is factorial of n. The number sigma 1 is the sum of the elements of A1, A2, An. Let us compute the number of elements of A1. A1 are the permutations of X that keep 1 at its place.
276.5
So it’s a set, essentially, of the permutations of 2n, whose number of elements is factorial of n minus 1. And so we get sigma 1 equal to n times, and factorial of n minus 1, which is factorial of n. Let us now compute sigma 2. Well, sigma 2 is the sum of the number of elements of the intersections 2 by 2. Let us consider the intersection, for instance, of A1 with A2. These are the permutations that keep 1 at its place and 2 at its place. So these permutations are as many as other permutations of the remaining terms 3, 4, n. So they are factorial of 2 minus 2.
325.3
How many are the intersections, 2 by 2 of the n sets? Well, they are binomial n over 2 such [? of ?] these intersections. And so sigma 2 will be equal to the binomial of n over 2 times factorial of n minus 2, which gives a factorial of n divided by factorial of 2 elements.
353.8
Similarly, the number of elements of the intersection of A1, with A2, with Am for any m from 1 to n, well, is equal to the number of permutations of the sequence n plus 1, n plus 2, n, with n minus m terms. So it is equal to factorial of n minus m. And therefore, sigma m turns out to be equal to factorial of n divided factorial of m. So we put all together, and we apply the Inclusion-Exclusion Principle. And so we get n factorial times 1 minus 1 plus 1 over 2 factorial of 2 and so on, which is exactly the formula that we wanted to prove.
404.2
We are now in the position to solve the hat problem. In how many ways can the n hats be redistributed in such a way that nobody receives his own hat? Well, the n, the number of derangements of the sequence 1, 2, 3, n, but we are also now able to compute the probability that nobody will receive his own hat, if hats are taken at random at the exit of the restaurant. Indeed, X, the set of permutations of 1n, is an appropriate space for uniform probability, because if hats are taken randomly, each permutation had the same opportunity to appear. And there are n factorial such permutations.
451.1
So the probability that nobody will receives his own hat is simply the number of derangements divided by factorial of n, which is 1 minus 1 over 1 plus 1 over factorial of 2 and so on. And notice that this quantity– since this is the first portion of the development, the Maclaurin Taylor development of e to minus 1– well, this stands to 1 over e, the Euler number, as n times 2 plus infinity. So it is an opportunity to approximate the Euler number. It is just enough to make hundreds of experiments with lots of people.
504.5
And the quotient of the number of times that nobody receives his own hat, divided the number of trials, returned to 1 divided to the Euler number.

Imagine you distribute 10 Books numbered from 1 to 10 to Students 1,2,…,10. How many ways are there to redistribute the books in such a way that nobody receives the book he had before? Translated into mathematical terms, how many are the derangements of the sequence ((1,2,…,10))?

You can access the content of the video in the PDF file at the bottom of this step.

This article is from the free online

Combinatorics: Strategies and Methods for Counting

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education