tg

tg
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.
at
Post a Comment
Subscribe to: Post Comments (Atom)