|
|
|
|
|
Let  be the symmetric group of order  . A permutation
 without a fixed point (that is,
 for any
 ) is called a derangement.
In combinatorial theory, one is usually interested in the number  of derangements in  . It is clear that
 , and  . It is also not difficult to calculate  for small  . For general  , one can appeal to the principle of inclusion-exclusion. Let  denote the collection of permutations that fix  . Then the collection of  of derangments in  is just the complement of
in  . Let
 and  be the  -fold intersection of members of  (that is, each member of  has the form
 ). We can interpret a member of  as a set of permutations that fix  elements from
 . The cardinality of each of these members is  . Furthermore, there are
 members in  . Then,
With this equation, one can easily derive the recurrence relation
Apply this formula twice, we are led to another recurrence relation
Application. A group of  men arrive at a party and check their hats. Upon departure, the hat-checker, being forgetful, randomly (meaning that the distribution of picking any hat out of all possible hats is a uniform distribution) hands back a hat to each man. What is the probability  that no man receives his own hat? Does this probability go to 0 as  gets larger and larger?
Answer: According to the above calculation,
Therefore,
|
"derangement" is owned by CWoo. [ full author list (2) ]
|
|
(view preamble)
Cross-references: uniform distribution, distribution, forgetful, group, application, recurrence relation, equation, cardinality, intersection, complement, fix, collection, principle of inclusion-exclusion, calculate, clear, number, theory, fixed point, permutation, order, symmetric group
There is 1 reference to this entry.
This is version 4 of derangement, born on 2006-07-14, modified 2006-10-14.
Object id is 8144, canonical name is Derangement.
Accessed 1496 times total.
Classification:
| AMS MSC: | 05A05 (Combinatorics :: Enumerative combinatorics :: Combinatorial choice problems ) | | | 05A15 (Combinatorics :: Enumerative combinatorics :: Exact enumeration problems, generating functions) | | | 60C05 (Probability theory and stochastic processes :: Combinatorial probability) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![$\displaystyle n!-\Big[\sum_{S\in I_1}\vert S\vert-\cdots+(-1)^k\sum_{S\in I_k}\vert S\vert+\cdots+(-1)^n\sum_{S\in I_n}\vert S\vert\Big]$](http://images.planetmath.org:8080/cache/objects/8144/l2h/img35.png "$\displaystyle n!-\Big[\sum_{S\in I_1}\vert S\vert-\cdots+(-1)^k\sum_{S\in I_k}\vert S\vert+\cdots+(-1)^n\sum_{S\in I_n}\vert S\vert\Big]$")
![$\displaystyle n!-\Big[{n\choose 1}(n-1)!-\cdots+(-1)^k {n\choose k} (n-k)!+\cdots+(-1)^n {n\choose n} (n-n)!\Big]$](http://images.planetmath.org:8080/cache/objects/8144/l2h/img37.png "$\displaystyle n!-\Big[{n\choose 1}(n-1)!-\cdots+(-1)^k {n\choose k} (n-k)!+\cdots+(-1)^n {n\choose n} (n-n)!\Big]$")
![$\displaystyle n!-\Big[ \frac{n!}{1!}-\cdots +(-1)^k\frac{n!}{k!}+\cdots +(-1)^n\frac{n!}{n!}\Big]$](http://images.planetmath.org:8080/cache/objects/8144/l2h/img39.png "$\displaystyle n!-\Big[ \frac{n!}{1!}-\cdots +(-1)^k\frac{n!}{k!}+\cdots +(-1)^n\frac{n!}{n!}\Big]$")
![$\displaystyle d(n)=(n-1)\big[d(n-1)+d(n-2)\big].$](http://images.planetmath.org:8080/cache/objects/8144/l2h/img43.png "$\displaystyle d(n)=(n-1)\big[d(n-1)+d(n-2)\big].$"){kind=small}
