ONE MORE STEP TOWARD BETTER TOMORROW : CHAPTER 11 - example of envelopes problem in permutation & combinations

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.

Tuesday, 5 August 2014

CHAPTER 11 - example of envelopes problem in permutation & combinations

No comments:

https://www.youtube.com/TarunGehlot