Derangements

From Wikipedia

In combinatorial mathematics, a derangement is a permutation of the elements of a set in which no element appears in its original position.

For example, if we have the set ${A, B, C}$ , there are $6$ permutations

$ABC, ACB, BAC, BCA, CAB, CBA$

But only $2$ of them are derangements – $BCA$ and $CAB$

I did a practical question on this here. In that question I used a tree diagram, but there must be a way to determine the number of derangements given $n$ elements.

We know $3$ elements has $2$ derangements, what about $4$ elements? We know there are $4!=24$ permutations

ABCD	BACD	CABD	DABC
ACBD	BADC	CADB	DACB
ACDB	BCAD	CBAD	DBAC
ABDC	BCDA	CBDA	DBCA
ADBC	BDAC	CDAB	DCAB
ADCB	BDCA	CDBA	DCBA

I have highlighted the derangements. when $n=4$ there are $9$ derangements.

Let’s try to generalise.

In how many ways can one element be in its original position?
$\begin{pmatrix}4\\1\end{pmatrix} \times 3!=24$
Choose one element from the 4 to be in its original position, and then arrange the remaining three elements.

So far, we have $D_3=4!-\begin{pmatrix}4\\1\end{pmatrix} \times 3!=0$

Clearly we are counting some arrangements multiple times, for example ABDC has A and B in the correct position, so we need to add all of the arrangements with $2$ elements in their original position.
In how many ways can two elements be in their original position?
$\begin{pmatrix}4\\2\end{pmatrix} \times 2!=12$

So now we have, $D_3=4!-\begin{pmatrix}4\\1\end{pmatrix} \times 3!+\begin{pmatrix}4\\2\end{pmatrix} \times 2!=12$

But once again we have counted some arrangements multiple times, so we need to subtract all of the arrangements with $3$ elements in their original position.
In how many ways can three elements be in their original position?
$\begin{pmatrix}4\\3\end{pmatrix} \times 1!=4$

So now we have, $D_3=4!-\begin{pmatrix}4\\1\end{pmatrix} \times 3!+\begin{pmatrix}4\\2\end{pmatrix} \times 2!-\begin{pmatrix}4\\3\end{pmatrix} \times 1!=8$

We now need to add all of the arrangements with $4$ elements in their original position.
In how many ways can four elements be in their original position?
$\begin{pmatrix}4\\4\end{pmatrix} \times 0!=1$

So now we have, $D_4=4!-\begin{pmatrix}4\\1\end{pmatrix} \times 3!+\begin{pmatrix}4\\2\end{pmatrix} \times 2!-\begin{pmatrix}4\\3\end{pmatrix} \times 1!+\begin{pmatrix}4\\4\end{pmatrix} \times 0!=9$

Hence,

$D_n=\begin{pmatrix}n\\0\end{pmatrix}\times n!-\begin{pmatrix}n\\1\end{pmatrix}\times (n-1)!+\begin{pmatrix}n\\2\end{pmatrix}\times (n-2)!-... \mp \begin{pmatrix}n\\n\end{pmatrix}\times 0!$

Which we can simplify to

$D_n=\Sigma_{i=0}^{n}(-1)^n\begin{pmatrix}n\\i\end{pmatrix}\times(n-i)!$

Leave a Reply Cancel reply

Recent Posts

Categories

Archives