Derangements

$\underline{Theory}$

Derangement of an arrangement of distinct objects, is defined as the rearrangement of the objects in which no object is placed in its original position.

For example, $bca$ is a valid derangement of the word $abc$, while $bac$ is not because $c$ occurs in the $3\xasuper{rd}$ position in both the original word and the rearrangement.

Derangement of an $n$ object arrangement is denoted by $D_n$ or $!n$, and is given by:

$!n = n! \displaystyle\sum\limits_{k = 0}^{n}\dfrac{(-1)^k}{k!}$

$\underline{Derivation}$

To be able to understand the derivation of this formula we will take an example, and use that to understand the derivation.

Let us find the number of derangements of the word $abcd$.

The total number of arrangements of the word $abcd$ without any restriction is $4! = 24$.

Now we need to subtract the cases where one or more letter is assigned its original position.

We can choose the one letter in $\xacomb{4}{1}$ ways, and arrange the remaining $(4-1)$ in $(4-1)! = 3!$ ways.

-----------book page break-----------

Therefore, the total number of cases where letters do not appear in their original position seems to be:

$4! - (\xacomb{4}{1}\times 3!) = 24 - 24 = 0$

But this cannot be correct, because there surely are ways to rearrange the letters where no letter appears in the same position.

We are getting this error because whatever we are subtracting includes some double counting.

Let us say we chose the letter $a$ to be in its original position, and the remaining $3$ can be arranged in $3!$ ways.

This $3!$ ways include cases where the letters $b$ or $c$ or $d$ can be in their original position.

These cases will again be recounted when we choose $b$ to be in its original position.

So let's see for how many cases $2$ letters will be in their respective original position, and add it back.

The number of ways two letters can be selected is $\xacomb{4}{2}$ and the remaining can be arranged in $(4-2)!$ ways.

Therefore there are a total of $\xacomb{4}{2} \times (4 - 2)!$

Since we double subtracted this, we need to add it back. Therefore, we get our number of arrangements as:

$4! - \xacomb{4}{1}\times (4-1)! + \xacomb{4}{2}\times (4-2)!$

While adding back the cases of $2$ letters occupying their original positions, we are adding as an extra, the number of arrangements where $3$ letters occupy their original positions, which we need to subtract again.

This can happen in $\xacomb{4}{3} \times (4 - 3)!$ ways.

-----------book page break-----------

Therefore, our new count of derangements become:

$4! - \xacomb{4}{1}\times (4-1)! + \xacomb{4}{2}\times (4-2)! - \xacomb{4}{3} \times (4 - 3)!$

Moving ahead with similar logic, when we selected $3$ letters to be in correct position, we have double-subtracted the case with all $4$ letters in correct position.

That can happen in $\xacomb{4}{4} \times (4-4)!$ ways and we need to add that back.

Therefore, our final count of derangements is:

$4! - \xacomb{4}{1}\times (4-1)! + \xacomb{4}{2}\times (4-2)! - \xacomb{4}{3} \times (4 - 3)! + \xacomb{4}{4} \times (4-4)!$

Since we are alternating between subtracting and adding the errors, we can write this as:

$4! + (-1)^1\times \xacomb{4}{1}\times (4-1)! + (-1)^2\times \xacomb{4}{2}\times (4-2)! $$+ (-1)^3\times \xacomb{4}{3} \times (4 - 3)! + (-1)^4\times \xacomb{4}{4} \times (4-4)!$

For the generic case of $n$ objects we will get the count of derangements as:

$n! + (-1)^1 \times \xacomb{n}{1}\times (n-1)! + (-1)^2 \times \xacomb{n}{2}\times (n-2)! + ...$$ + (-1)^n \times \xacomb{n}{n}\times (n-n)!$

Re-writing the first term in a similar way as the rest we get:

$(-1)^0 \times \xacomb{n}{0} \times (n - 0)! + (-1)^1 \times \xacomb{n}{1}\times (n-1)! + (-1)^2 \times \xacomb{n}{2}\times (n-2)! + ...$$ + (-1)^n \times \xacomb{n}{n}\times (n-n)!$

We can write the $r\xasuper{th}$ term, where $0 \le r \le n$ of the above series as:

$(-1)^r \times \xacomb{n}{r} \times (n - r)!$

$= (-1)^r \times \dfrac{n!}{r!(n-r)!} \times (n - r)! = (-1)^r \times \dfrac{n!}{r!}$

-----------book page break-----------

Therefore, we get the count of derangements for $n$ objects as:

$!n = (-1)^0 \times \dfrac{n!}{0!} + (-1)^1 \times \dfrac{n!}{1!} + ... + (-1)^n \times \dfrac{n!}{n!}$

$\Rightarrow !n =n!\left\{(-1)^0 \times \dfrac{1}{0!} + (-1)^1 \times \dfrac{1}{1!} + ... + (-1)^n \times \dfrac{1}{n!}\right\}$

$\Rightarrow !n =n!\left\{\dfrac{(-1)^0 }{0!} + \dfrac{(-1)^1}{1!} + ... + \dfrac{(-1)^n}{n!}\right\}$

$\Rightarrow !n = n! \displaystyle\sum\limits_{k = 0}^{n}\dfrac{(-1)^k}{k!}$

$\underline{Finding\ Derangements\ With\ Identical\ Objects}$

We will understand this with another example. Let's try to answer the following question.

How many derangements are possible for the word $GOOD$ where the two $O$s are identical (where one $O$ cannot take the position of the other $O$)?

To begin with we can treat the $O$s as distinct object by marking them as $O_1$ and $O_2$, and compute the derangements.

The number of derangements for the word $GO_1O_2D$ is:

$!4 = 4! \displaystyle\sum\limits_{k = 0}^{4}\dfrac{(-1)^k}{k!}$

$= \dfrac{4!}{0!} - \dfrac{4!}{1!} + \dfrac{4!}{2!} - \dfrac{4!}{3!} + \dfrac{4!}{4!}$

-----------book page break-----------

$= 24 - 24 + 12 - 4 + 1 = 9$

Now let us list down all the $9$ derangements for $GO_1O_2D$, as follows:

$\begin{matrix}O_1 & G & D & O_2 \\ O_1 & D & G & O_2 \\ O_1 & O_2 & D & G \\ O_2 & G & D & O_1 \\ O_2 & D & G & O_1 \\ O_2 & D & O_1 & G \\ D & G & O_1 & O_2 \\ D & O_2 & G & O_1 \\ D & O_2 & O_1 & G\end{matrix}$

Now we will need to apply the correction for the following three cases:

$I)$ $O_1$ takes the original position of $O_2$

$II) $$O_2$ takes the original position of $O_1$

$III)$ $O_1$ takes the original position of $O_2$ and $O_2$ takes the original position of $O_1$

$\underline{Case\ I:}$

For this we can swap $O_1$ and $O_2$ in the original word and fix the position of $O_1$ and find the derangement of the other letters.

Let us find the derangements for the word:

$G\ O_2\ \bbox[#dddddd, 1pt]{O_1}\ D$

We know that:

$!3 = \dfrac{3!}{0!} - \dfrac{3!}{1!} + \dfrac{3!}{2!} - \dfrac{3!}{3!}$

$ = 6 - 6 + 3 - 1 = 2$

Those two derangements are:

$O_2\ D\ \bbox[#dddddd, 1pt]{O_1}\ G$

$D\ G\ \bbox[#dddddd, 1pt]{O_1}\ O_2$

-----------book page break-----------

$\underline{Case\ II:}$

This is exactly the same as $Case\ I$ but this time we swap and fix $O_2$ and find the derangement for the word:

$G\ \bbox[#dddddd, 1pt]{O_2}\ O_1\ D$

We will have $!3 = 2$ derangements, which are:

$O_1\ \bbox[#dddddd, 1pt]{O_2}\ D\ G$

$D\ \bbox[#dddddd, 1pt]{O_2}\ G\ O_1$

As we can see that neither $Case\ 1$ or $Case\ 2$ has the condition where $O_2$ occupiies the position of $O_1$ and vice versa.

So we will need to apply the correction in $Case\ III$

$\underline{Case\ III:}$

Now we can swap the two $O$s and fix both of them, and then find the derangements of the remaining $2$, that is we find the deragnements for the word:

$G\ \bbox[#dddddd, 1pt]{O_2}\ \bbox[#dddddd, 1pt]{O_1}\ D$

$!2 = \dfrac{2!}{0!} - \dfrac{2!}{1!} + \dfrac{2!}{2!} = 2 - 2 + 1 = 1$

And the derangement is easy to see, which is:

$D\ \bbox[#dddddd, 1pt]{O_2}\ \bbox[#dddddd, 1pt]{O_1}\ G$

Therefore, the total number of derangements possible after applying the corrections for two $O$s, is:

$9 - 2 - 2 - 1 = 4$

and the list of derangements so far is:

$O_1\ G\ D\ O_2$

$O_1\ D\ G\ O_2$

$O_2\ G\ D\ O_1$

$O_2\ D\ G\ O_1$

-----------book page break-----------

Now all we need to do is divide by $2!$ to take care of the two $O$s in our cases:

Therefore, the number of valid derangements is $\dfrac{4}{2!} = 2$

And the final derangements are:

$O\ G\ D\ O$

$O\ D\ G\ O$