1
$\begingroup$

I can't really understand how the recursive formula for derangements is derived,i.e I cant see how the patterns of it occur.

From Wikipedia:

Suppose that there are $n$ persons who are numbered $1, 2, ..., n.$ Let there be $n $hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as his/her number. Let us assume that the first person takes hat $ i$. There are $n − 1$ ways for the first person to make such a choice. There are now two possibilities, depending on whether or not person $i$ takes hat $1$ in return:

Person $i$ does not take the hat $1$. This case is equivalent to solving the problem with $n − 1$ persons and $n − 1$ hats: each of the remaining $n − 1$ people has precisely 1 forbidden choice from among the remaining $n − 1$ hats (i's forbidden choice is hat 1). Person $i$ takes the hat $1$. Now the problem reduces to $n − 2$ persons and $n − 2$ hats. From this, the following relation is derived:

$!n = (n - 1) (!(n-1) + !(n-2)). $

In this particular example I do not understand why we take care of the case when person $i$ takes hat $1$ or not. When I think about derangements i see that the first person has $n-1$ choices ,so the rest of the people ,but,and here's another conceptual problem, how do we know that if we continue to count like this the last person, as its only and one choice ,won't have a hat of the same number? Also how would one calculate derangements with the formula above ? I am a visual learner ,so if you can provide some kind of mental images to help the understanding of the concept I would appreciate more.

P.S: Forgive me if I've made some english mystakes and feel free to edit in case..

(I've checked if this question was a duplicate but i didn't find other questions asking for some kind of intuitive argument for derangements)

$\endgroup$
  • $\begingroup$ Some of your Readers may not be familiar with or recognize immediately the notation $!n$ denoting the number of derangements of $n$ items, i.e. permutations without fixed points. Explaining this notation briefly before using it would be an improvement. $\endgroup$ – hardmath Oct 5 '15 at 21:11
  • $\begingroup$ if you would explain it to me,because i dont understand it either...I've edited btw to make clear i dont understand it too $\endgroup$ – Nameless Oct 5 '15 at 21:13
  • $\begingroup$ Okay, did you understand the definition of derangements (as opposed to the notation), that these are a subset of all permutations? There are $n! = n\cdot (n-1)\cdot \ldots \cdot 1$ permutations, and a shortcut notation for the number of derangements is $!n$. More about the notations for derangements is shown in the Wikipedia article you found. $\endgroup$ – hardmath Oct 5 '15 at 21:16
  • $\begingroup$ sure i see that those are subsets,i've also worked out some exercises but the method i use to calculate those subsets is through some Venn diagram i draw,but of course i do this for exercises where i dont have a great number of objects to count..if the number of objects is really big it would take me an entire life to sketch all of these diagrams $\endgroup$ – Nameless Oct 5 '15 at 21:19
2
$\begingroup$

As the Wikipedia article on Derangement mentions in its second paragraph, the number of permutations of $n$ items that have no fixed points (derangements) is usually denoted $D_n$, $d_n$, or $!n$. This last is a cute rearrangement of the exclamation point in factorial $n!$, but it might be the source of some confusion here.

So let's use the notation $D_n$ instead. Since derangements are a proper subset of permutations, we have $D_n \lt n!$. The Question here is about "intuition" for a recursive relationship for $D_n$:

$$ D_n = (n-1) ( D_{n-1} + D_{n-2} ) $$

Together with initial values $D_1 = 0$ and $D_2 = 1$, the relation above allows the recursive computation of $D_n$ for all positive integers $n$.

Note the argument given in the Wikipedia article. We get the initial factor $n-1$ by considering which "hat" is assigned to the first person to leave, considering those assignments of hats as a proxy for permutations of the people themselves. As we avoid giving the first person their own hat, there are $n-1$ possibilites.

Let $k \gt 1$ identify which hat is given to the first person. We break down the cases in two mutually exclusive subsets, depending on whether the owner of the $k$-th hat (1) gets a hat that does not belong to the first person or (2) gets the hat that belongs to the first person.

The second case, in which the person who owns hat $k$ gets assigned hat $1$ (so that this person has swapped hats with the first person) is perhaps the easiest to understand. So let's get that ironed out.

Since in the second case those two people (the first person having the $k$-th hat and the owner of that hat) have swapped hats, the total permutation is a derangement exactly when the remaining $n-2$ hats are assigned in a derangement. Thus the second case occurs in $D_{n-2}$ ways, corresponding to the derangement on the remaining hats (or people).

The first case, in which the person who owns hat $k$ does not get assigned hat $1$, is a little tricky to follow. Here's a different way to state the idea. Let the first person and the $k$-hat owning person switch places for a moment. The first person goes back inside and gives the $k$-hat back to its owner temporarily, who then steps outside. Now make a derangement of the $n-1$ hats and their owners who are still inside. There are $D_{n-1}$ ways this can be done. Finally the first person steps outside, carrying a hat belonging to someone else, but not the $k$-hat since it was being held by its owner outside.

These two people switch one last time. The first person now again has the $k$-th hat, and the owner of that hat gets one not belonging to them and not belonging to the first person (because the hat brought outside by the first person this second time, again did not belong to them).

Putting these counting of subcases together we get the recursive relationship above, $D_n$ is $n-1$ times the sum of the $D_{n-1}$ first cases and the $D_{n-2}$ second cases.

$\endgroup$
  • $\begingroup$ thanks for your answer and for the time you've put to write this all down @hardmath,now it's clear $\endgroup$ – Nameless Oct 6 '15 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.