CHAPTER 11 - example of envelopes problem in permutation & combinations
Find the number of ways in which different letters can be taken out of their addressed envelopes and put back into the envelopes in such a way that all letters are in the wrong envelope.
The problem of rearranging objects so that each object is assigned to a place different from its original place is referred to as the problem of dearrangments. Here, we need to find out the number of dearrangements possible with letters and envelopes.
Let us denote by the number of dearrangements possible with things. We will attempts a general solution, that is for an arbitrary , and then substitute
Denote by the letter and by , the original envelope of the letter.
Consider the envelope . It can be assigned a wrong letter in ways. Suppose that we assign the letter to .
The dearrangements that can now arise can be divided into two mutually exclusive classes:
(i) Those in which is assigned to
(ii) Those in which is not assigned to
If is assigned to , we have the following configuration:
In this case, we have a remaining of letters which can be dearranged in ways.
Suppose the other case now, where we do not assign to . In this case, we have letters to dearrange ( will also be counted as a letter to be dearranged since it is being assigned to an envelope other than ). This can be done in ways.
Thus, if we give to , the total dearrangements possible are
Since can assigned a wrong letter in ways, the overall total number of dearrangements is
We have thus related the order ‘dearrangements–coefficient’ to lower order coefficients.
We now have to somehow use this relation to obtain only in terms of . This is how we do it:
But if we substitute we get
We substitute back into to get
It is obvious that since one letter cannot be dearranged while because two letters can be dearranged in only one way : by exchanging them.
We still have not obtained a relation involving only . We do it using repeatedly
Now we substitute successively and add the corresponding sides of all the relations so obtained to get
Since , we finally get
This is the number of de arrangements possible with things For , we have
Thus, there are ways to rearrange the letters back into their envelopes so that each letter goes to a wrong envelope.
Since is a small number, we could have worked out an alternative solution as follows:
You are urged to work out the solution by this way yourself.