derangement


Let Sn be the symmetric group of order n1. A permutationMathworldPlanetmath ϕSn without a fixed pointPlanetmathPlanetmath (that is, ϕ(i)i for any i{1,,n}) is called a derangementMathworldPlanetmath.

In combinatorial theory, one is usually interested in the number d(n) of derangements in Sn. It is clear that d(1)=0,d(2)=1, and d(3)=2. It is also not difficult to calculate d(n) for small n. For general n, one can appeal to the principle of inclusion-exclusion. Let Ai denote the collectionMathworldPlanetmath of permutations that fix i. Then the collection of A of derangments in Sn is just the complement of

A1A2An

in Sn. Let C={A1,,An} and Ik be the k-fold intersectionMathworldPlanetmath of members of C (that is, each member of Ik has the form Aj1Ajk). We can interpret a member of Ik as a set of permutations that fix k elements from {1,,n}. The cardinality of each of these members is (n-k)!. Furthermore, there are (nk) members in Ik. Then,

d(n) = |A|=|Sn|-|A1AkAn|
= n!-[SI1|S|-+(-1)kSIk|S|++(-1)nSIn|S|]
= n!-[(n1)(n-1)!-+(-1)k(nk)(n-k)!++(-1)n(nn)(n-n)!]
= n!-[n!1!-+(-1)kn!k!++(-1)nn!n!]
= n!k=0n(-1)kk!

With this equation, one can easily derive the recurrence relation

d(n)=nd(n-1)+(-1)n.

Apply this formulaMathworldPlanetmathPlanetmath twice, we are led to another recurrence relation

d(n)=(n-1)[d(n-1)+d(n-2)].

Application. A group of n men arrive at a party and check their hats. Upon departure, the hat-checker, being forgetful, randomly (meaning that the distributionPlanetmathPlanetmath of picking any hat out of all possible hats is a uniform distributionMathworldPlanetmath) hands back a hat to each man. What is the probability p(n) that no man receives his own hat? Does this probability go to 0 as n gets larger and larger?

Answer: According to the above calculation,

p(n)=d(n)n!=k=0n(-1)kk!.

Therefore,

limnp(n)=1e0.368.
Title derangement
Canonical name Derangement
Date of creation 2013-03-22 16:05:04
Last modified on 2013-03-22 16:05:04
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Definition
Classification msc 05A15
Classification msc 05A05
Classification msc 60C05