Derangement Calculator
Discover the fascinating world of derangements! Calculate the number of permutations where no element stays in its original place.
Result:
Calculation Steps:
What are Derangements?
In combinatorics, a derangement is a permutation of the elements of a set such that no element appears in its original position. For example, if we have the set {(1, 2, 3)}, the derangements are (2, 3, 1) and (3, 1, 2). The number of derangements of a set of size n is denoted by D(n) or !n.
Formula
The number of derangements D(n) can be calculated using the recursive formula:
- D(0) = 1
- D(1) = 0
- D(n) = (n - 1) * [D(n-1) + D(n-2)] for n ≥ 2
Alternatively, it can be calculated using the subfactorial formula, which is closely related to the factorial:
D(n) = n! * [1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!]
Use Cases
Derangements have applications in various fields, including:
- Probability: Calculating probabilities in scenarios where no match is desired.
- Statistics: In problems involving permutations and arrangements.
- Computer Science: Algorithm analysis and problem-solving.
- Puzzles and Games: In designing and solving combinatorial puzzles.