tgt

## Tuesday, 5 August 2014

### CHAPTER 11 - example of envelopes problem in permutation & combinations

 Example: 1
 Find the number of ways in which $5$ different letters can be taken out of their $5$ addressed envelopes and put back into the envelopes in such a way that all letters are in the wrong envelope.
 Solution: 1
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 $5$ letters and $5$ envelopes.
Let us denote by $\,{D_n}$ the number of dearrangements possible with $n$ things. We will attempts a general solution, that is for an arbitrary $n$, and then substitute $n = 5$
Denote by ${L_i}$ the ${i^{th}}$ letter and by ${E_i}$, the original envelope of the ${i^{th}}$ letter.
Consider the envelope ${E_1}$. It can be assigned a wrong letter in $(n - 1)$ ways. Suppose that we assign the letter ${L_2}$ to ${E_1}$.
 $\begin{array}{l} {E_1}\,\,\,\,{E_2}\,\,\ldots \ldots \,\,{E_n}\\ \,\,\,\,\,\,\, \nwarrow \\ {L_1}\,\,\,\,{L_2}\,\,\ldots \ldots \,\,{L_n} \end{array}$
The dearrangements that can now arise can be divided into two mutually exclusive classes:
 (i) Those in which ${L_1}$ is assigned to ${E_2}$ (ii) Those in which ${L_1}$ is not assigned to ${E_2}$
If ${L_1}$ is assigned to ${E_2}$, we have the following configuration:
In this case, we have a remaining of $(n - 2)$ letters which can be dearranged in ${D_{n - 2}}$ways.
Suppose the other case now, where we do not assign ${L_1}$ to ${E_2}$. In this case, we have $(n - 1)$ letters to dearrange (${L_1}$ will also be counted as a letter to be dearranged since it is being assigned to an envelope other than ${E_2}$). This can be done in ${D_{n - 1}}$ ways.
Thus, if we give ${L_2}$ to ${E_1}$, the total dearrangements possible are ${D_{n - 1}} + {D_{n - 2}}.$
Since ${E_1}$ can assigned a wrong letter in $(n - 1)$ ways, the overall total number of dearrangements ${D_n}$ is
 ${D_n} = \left( {n - 1} \right)\left( {{D_{n - 1}} + {D_{n - 2}}} \right)$
We have thus related the ${n^{th}}$ order ‘dearrangements–coefficient’ ${D_n}$ to lower order coefficients.
We now have to somehow use this relation to obtain ${D_n}$ only in terms of $n$. This is how we do it:
 ${D_n} = \left( {n - 1} \right)\left( {{D_{n - 1}} + {D_{n - 2}}} \right)$ $\Rightarrow \,\,\,\, {D_n} - n{D_{n - 1}} = \left( { - 1} \right)\left( {{D_{n - 1}} - {\,^{\left( {n - 1} \right)}}{D_{n - 2}}} \right)$ $\ldots (1)$
But if we substitute $n \to \left( {n - 1} \right)$ we get
 ${D_{n - 1}} - \left( {n - 1} \right){D_{n - 2}} = \left( { - 1} \right)\left( {{D_{n - 2}} - \left( {n - 2} \right){D_{n - 3}}} \right)$ $\ldots (2)$
We substitute $(2)$ back into $(1)$ to get
 ${D_n} - n{D_{n - 1}} = {\left( { - 1} \right)^2}\left( {{D_{n - 2}} - \left( {n - 2} \right){D_{n - 3}}} \right)$ $= {\left( { - 1} \right)^3}\left( {{D_{n - 3}} - \left( {n - 3} \right){D_{n - 4}}} \right)\,\,\,\,\left\{ \begin{array}{l} {\rm{By\, the\, same\,}}\\ {\rm{ process}} \end{array} \right\}$ $\vdots \vdots$ $= {\left( { - 1} \right)^{n - 2}}\left( {{D_2} - 2{D_1}} \right)$
It is obvious that ${D_1} = 0$ since one letter cannot be dearranged while ${D_2} = 1$ because two letters can be dearranged in only one way : by exchanging them.
Thus,
 ${D_n} - n{D_{n - 1}} = {\left( { - 1} \right)^{n - 2}}$ $\ldots (3)$
We still have not obtained a relation involving only ${D_n}$. We do it using $(3)$ repeatedly
 ${D_n} - n{D_{n - 1}} = {\left( { - 1} \right)^{n - 2}} = {\left( { - 1} \right)^n}$ $\Rightarrow \,\,\,\, \dfrac{{{D_n}}}{{n!}} - \dfrac{{{D_{n - 1}}}}{{\left( {n - 1} \right)!}} = \dfrac{{{{\left( { - 1} \right)}^n}}}{{n!}}$ Division by $n!$
Now we substitute $n \to \left( {n - 1} \right),\,\,\,n \to \left( {n - 2} \right)\ldots$ successively and add the corresponding sides of all the relations so obtained to get
 $\dfrac{{{D_n}}}{{n!}} - \dfrac{{{D_1}}}{{1!}} = \dfrac{{{{\left( { - 1} \right)}^n}}}{{n!}} + \dfrac{{{{\left( { - 1} \right)}^{n - 1}}}}{{\left( {n - 1} \right)!}} + \dfrac{{{{\left( { - 1} \right)}^{n - 2}}}}{{\left( {n - 2} \right)!}} +\ldots + \dfrac{{{{\left( { - 1} \right)}^2}}}{{2!}}$
Since ${D_1} = 0$, we finally get
 ${D_n} = n!\left( {\dfrac{1}{{2!}} - \dfrac{1}{{3!}} + \dfrac{1}{{4!}} - \ldots \dfrac{{{{\left( { - 1} \right)}^n}}}{{n!}}} \right)$ $= n!\left( {1 - \dfrac{1}{{1!}} + \dfrac{1}{{2!}} - \dfrac{1}{{3!}} +\ldots \dfrac{{{{\left( { - 1} \right)}^n}}}{{n!}}} \right)$$\left\{ \begin{array}{l} {\rm{The\, first\, two\, terms \,''1''}}\,{\rm{and}}\,\,''\dfrac{{\rm{1}}}{{{\rm{1!}}}}''\\ {\rm{ are\, just\, added \,to\, make\, the\, }}\\ {\rm{series\, look\, more\, sequenced\,}} \end{array} \right\}$
This is the number of de arrangements possible with $n$ things For $n = 5$, we have
 ${{\rm{D}}_{\rm{5}}} = 5!\left( {1 - \dfrac{1}{{1!}} + \dfrac{1}{{2!}} - \dfrac{1}{{3!}} + \dfrac{1}{{4!}} - \dfrac{1}{{5!}}} \right)$ $=44$
Thus, there are $44$ ways to rearrange the letters back into their envelopes so that each letter goes to a wrong envelope.
Since $n = 5$ is a small number, we could have worked out an alternative solution as follows:
 ${\rm{No}}{\rm{. \,of \,dearrangemets }} = \,\,\left\{ \begin{array}{l} {\rm{Total\, No}}{\rm{. \,of\, arrangements\, -\, }}\\ {\rm{No}}{\rm{.\, of \,ways\, in\, which \,all\, letters\, go \,to \,}}\\ {\rm{correct\, envelopes \,- \, No}}{\rm{. \,of\, ways\, in\, }}\\ {\rm{which\, one\, letter\, goes\, to \,incorrect\, envelope\, -\, }}\\ {\rm{No}}{\rm{.\, of\, ways\, in\, which\, two \,letters\, go \,to\, incorrect\, }}\\ {\rm{envelopes \, -\, }}\ldots \ldots {\rm{and\, so\, on\,}} \end{array} \right\}$
You are urged to work out the solution by this way yourself.