Question

Explain Derangements. Write the formula and give examples.

Answer 1

Hint: Here, we will use an example to explain derangements. Also, we will state the formula for the number of derangements of a set with \[n\] objects. A derangement can also be called a permutation with no fixed points.

Complete step-by-step answer:
A permutation of the elements of a set where no element remains at the same place is called a derangement. It is denoted by \[!n\] or \[{D_n}\].
The number of derangements of a set with \[n\] objects is given by the formula \[{D_n} = n!\sum\limits_{k = 0}^n {\dfrac{{{{\left( { - 1} \right)}^k}}}{{k!}}} \].
For example: Suppose that \[S\] represents the set \[\left\{ {a,b,c} \right\}\]. Here, \[a\] comes at the first place, \[b\] comes at the second place, and \[c\] comes at the third place.
The elements of the set \[\left\{ {a,b,c} \right\}\] can be arranged as \[\left\{ {a,b,c} \right\}\], \[\left\{ {a,c,b} \right\}\], \[\left\{ {c,b,a} \right\}\], \[\left\{ {b,a,c} \right\}\], \[\left\{ {c,a,b} \right\}\], and \[\left\{ {b,c,a} \right\}\].
The derangements are the permutations with no fixed points. This means that the element \[a\] must not come at the first place, \[b\] must not come at the second place, and \[c\] must not come at the third place.
We can observe that in \[\left\{ {a,b,c} \right\}\], \[\left\{ {a,c,b} \right\}\], \[\left\{ {c,b,a} \right\}\], and \[\left\{ {b,a,c} \right\}\], there is at least one element \[a\], \[b\], or \[c\] which remains at the same place as in the set \[S = \left\{ {a,b,c} \right\}\].
Therefore, the derangements of the set \[S\] are \[\left\{ {c,a,b} \right\}\] and \[\left\{ {b,c,a} \right\}\].
Some other examples of derangements:
The number of ways in which five students A, B, C, D, and E, grade their five tests, such that no student grades his own test.
The number of ways in which 4 balls (red, white, blue, green respectively) are placed in 4 boxes (red, white, blue, green respectively) such that no ball is put into the box having the same colour.

Note: We can check the derangement formula in the example given in the solution.
There are 3 elements in the set \[S\].
Substituting \[n = 3\] in the formula for number of derangements, we get
\[\begin{array}{l} \Rightarrow {D_n} = 3!\sum\limits_{k = 0}^3 {\dfrac{{{{\left( { - 1} \right)}^k}}}{{k!}}} \\ \Rightarrow {D_n} = 3!\left[ {\dfrac{{{{\left( { - 1} \right)}^0}}}{{0!}} + \dfrac{{{{\left( { - 1} \right)}^1}}}{{1!}} + \dfrac{{{{\left( { - 1} \right)}^2}}}{{2!}} + \dfrac{{{{\left( { - 1} \right)}^3}}}{{3!}}} \right]\\ \Rightarrow {D_n} = 6\left[ {\dfrac{1}{1} + \dfrac{{ - 1}}{1} + \dfrac{1}{2} + \dfrac{{ - 1}}{6}} \right]\end{array}\]
Simplifying the expression, we get
\[\begin{array}{l} \Rightarrow {D_n} = 6\left[ {1 - 1 + \dfrac{1}{2} - \dfrac{1}{6}} \right]\\ \Rightarrow {D_n} = 6\left[ {\dfrac{{3 - 1}}{6}} \right]\\ \Rightarrow {D_n} = 6\left[ {\dfrac{2}{6}} \right]\\ \Rightarrow {D_n} = 2\end{array}\]
Therefore, we have checked that the number of derangements is 2, that is \[\left\{ {c,a,b} \right\}\] and \[\left\{ {b,c,a} \right\}\].