0
$\begingroup$

im missing something and i cant figure out what. Ive seen a proof of the formula for the number of derangements (permutations with no fixed points) using inclusion-exclusion and it makes perfect sense to me. I just cant wrap my head around why it isn't much simpler than that.

By my logic, assuming F is the permutation, the first element of {1,...,n} has n-1 possible mappings, the second element can be mapped anywhere except for itself and F(1), thus n-2 possibilities and so on. So why isn't the number of derangements simply (n-1)!?

Please help me see what im missing! Thank you

$\endgroup$
1
$\begingroup$

"the second element can be mapped anywhere except for itself and F(1)". sure, but what if the second element happens to be $F(1)$? You could rule this out, but then your "and so on" clause needs a little rephrasing

$\endgroup$
  • $\begingroup$ Yep, thats exactly what i missed, thanks! $\endgroup$ – Kai Jun 4 '16 at 13:41
1
$\begingroup$

Problem is in the line "the second element can be mapped anywhere except for itself and F(1), thus n-2 possibilities..".

What if $F(1) = 2$?

$\endgroup$
  • $\begingroup$ Thank you! Thats what i was looking for $\endgroup$ – Kai Jun 4 '16 at 13:44

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.