Derangements are arrangements of some number of objects into positions such that no object goes to its specified position. In the language of permutations, a derangement is a permutation of elements with no fixed point; that is, for all .
Letters and Envelopes Problem:
A kid has ‘N’ letters labeled Letter1, Letter2, …, LetterN and the corresponding ‘N’ addressed envelopes labeled Envelope1, Envelope2, ..., EnvelopeN. Then how many ways can the kid put the letters in the wrong envelope? (Letter1 should not go to Envelope1, Letter2 should not go to Envelope2, ...., LetterN should not go to EnvelopeN.)
Case 1: The kid has one envelope and one letter.
So the answer is 0 (zero). The kid did not have any option to insert the single letter into the wrong envelope. Hence the answer is zero.
Case 2: The kid has two envelopes and two letters.
So the answer is 1. If the kid placed the first letter in the wrong envelope, then the second letter automatically goes into the wrong envelope, so the possible choice is 1.
Case N: The kid has 'N' envelops and 'N' letters.
The answer is derangements of where
Let be the number of derangements for different objects, then
Let there be distinct objects with their distinct respective positions. Then the number of derangements is where is the number of ways of arranging the objects in such a way that at least one object goes to its right position.
To find , use PIE.
Let be the set of permutations in which the object goes into its right position. The goal is to find .
Observe that , and so on.
Then , and so on.
Now, using PIE,
Therefore, the number of derangements is
The above formula can be rewritten recursively as
In how many different ways can you rearrange the letters in the word MONKEY such that no letter in the new arrangement is in the same place as in the original word? (I.e. NOKEYM wouldn't work since O would be in the same place as it was in MONKEY.)
For more permutations quizzes, check out my other problems.
Note that is the partial sum of the Taylor series for evaluated at , so
So, for large , the probability that a permutation of objects is a derangement is approximately .
In fact, for any positive integer where the square brackets are the nearest integer function.
Here is another recursive formula for
Let be distinct objects with their respective containers and suppose goes into Then it gives rise to the following two cases:
Case 1: When goes to
Leaving out and there are derangements for objects:
Case 2: When goes to any other container:
Leaving out the number of these is the same as the number of derangements of objects including
If goes to in the derangement of objects, this corresponds to the derangement of objects where goes to and goes to
Thus, the total is
But the original assumption was that goes to . There are choices for , so
Mickey the mailman is very lazy. He has received 10 parcels to 10 different people. However, because he is lazy, he doesn't bother reading the address and delivers them off randomly. In how many ways can Mickey deliver the parcels such that no one gets the right parcel?
By the derangements formula, the number of possible derangements is
Therefore, there are a total of 1334961 ways to deliver the parcels such that no one gets the right parcel.
A teacher has six name tags to hand out to her six students. What is the probability that at least one student gets their name tag?
Using complementary probability, we see that there are ways to give out the name tags. The number of ways where nobody gets their name tag is
The probability is .
On the Christmas Eve, Santa was in a hurry to distribute gifts, so he asked the most innocent child in the country to help him in distributing 10 gifts to 10 different houses, where each house receives a gift.
To House #1, the boy gave the gift of House #2. At the end of the day, Santa informed the boy that he had not distributed a single gift to the correct place.
In how many ways can this happen?
Ignore the order in which the gifts were distributed. Consider just which gifts the houses received.
- This is part of my set "Fun is a Student's Right."
- You would also like "Let's play with polygons & circles."