The total number of elements to permute
Number of elements in their original position (for partial derangements)
Result
!n
=
-
About Derangements
A derangement is a permutation of elements where no element appears in its original position. In other words, it's a permutation with no fixed points.
Formulas
Complete Derangement (!n)
- Recursive formula: \(!n = (n-1)(!(n-1) + !(n-2))\)
- Explicit formula: \(!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}\)
- Approximation: \(!n \approx \lfloor \frac{n!}{e} + 0.5 \rfloor\)
Partial Derangement (!n,k)
- Formula: \(!n,k = \binom{n}{k} \cdot !(n-k)\)
- This counts permutations with exactly k fixed points
Examples
For n=3 elements {1,2,3}:
- Complete derangement (!3 = 2):
(2,3,1), (3,1,2) - Partial derangement (!3,1 = 2):
(1,3,2), (2,1,3), (3,2,1)
First Few Values
- !0 = 1
- !1 = 0
- !2 = 1
- !3 = 2
- !4 = 9
- !5 = 44
- !6 = 265
Applications
- Hat-check problem: returning n hats to n people randomly
- Matching problems where self-matching is forbidden
- Card shuffling and dealing problems
- Cryptography and random permutations
Note: The numbers grow very quickly. For large values of n, the result will be a very large number.