0
$\begingroup$

This question already has an answer here:

d(1)=0,d(2)=1,d(3)=2,d(4)=9,d(5)=44

Verify that d(5) = 44 and thus that the probability of a random rearrangement of 5 objects being a derangement is 44/120 = 0:3666

So i've been trying google/youtube to find examples on how to do these question but i had no luck. Can anyone demonstrate on how to do this question? and also what equation was used?

$\endgroup$

marked as duplicate by Ross Millikan, hardmath, apnorton, Dan Rust, Shuchang Dec 12 '13 at 1:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Google Derangements. $\endgroup$ – André Nicolas Dec 11 '13 at 23:15
  • $\begingroup$ @AndréNicolas Ahh just found the equation on how to prove d(5). what would i search for the 2nd half? $\endgroup$ – Unknownstarz Dec 11 '13 at 23:18
  • $\begingroup$ there are 120 permutations on 5 elements(5*4*3*2*1) and 44 of these are derangements. But I think you need to back up a little if you don't understand this. $\endgroup$ – Jorge Fernández Hidalgo Dec 11 '13 at 23:20
  • $\begingroup$ A lot of material about derangements, including a recurrence relation that can be used to count them, is summarized in a highly upvoted Answer to this Question. $\endgroup$ – hardmath Dec 11 '13 at 23:24
  • $\begingroup$ @hardmath Ahh cheers, thats what i needed to start me off thanks $\endgroup$ – Unknownstarz Dec 11 '13 at 23:25
1
$\begingroup$

Derangements follow a very simple recursive formula $d(n)=(n-1)(d(n-1)+d(n-2)$.

paraphrasing from wikipedia:

suppose we have a derangement on n objects if object number 1 is sent to place $j$ then exactly one of the following must be true for the derangement.

object $j$ is sent to place 1 (in which case the $(n-2)$ objects that are not 1 or $j$ can be any derangement on $n-2$ objects)

object $j$ is not sent to place 1. (then we know that the objects $\{2,3,4,5...n\}$ form a derangement on $n-1$ objects).

Combining this with the fact there are n-1 possible values for j (since 1 is not an option because it is a derangement) we get the [recursion] (http://en.wikipedia.org/wiki/Recursive_definition) $d(n)=n-1(d(n-1)+d(n-2))$

we start knowing $d(1)=0$ and $d(2)=1$. Therefore

$d(3)=2(1)=2$

$d(4)=3(2+1)=9$

$d(5)=4(9+2)=44$

Now: in general there are n! ways to rearrange n elements in a line. since 5!=120 there are 120 possible rearrangements (also called permutations). Now out of these 120 permutations only 44 are derangements. Assuming all of them are equally likely we get the probability of getting a derrangement is $\frac{44}{120}=\frac{11}{30}\approx 36.67%$

$\endgroup$
  • $\begingroup$ Cheers, help me more in depth $\endgroup$ – Unknownstarz Dec 11 '13 at 23:53

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