Random Permutations, Cards, and the Probability of a Derangement
# What is a Permutation?
A random permutation is a random ordering of a set of elements.
Example: Let the set be
Theorem 1.0: For a set
Proof: Since all elements in the set
Application 1.0: We will give an example in the context of card shuffling. To keep it simple, let us say we have four Aces with different suits. They are
# What is a Derangement?
Definition: A derangement is a permutation with no fixed points, such that no element is mapped to itself, that is,
Example 3.0: Let
Example 3.1: Let
Theorem 3.0: The function giving the number of distinct derangement on
Proof: Let the set of permutations of n objects be
Exactly one object is fixed: After fixing one object, we have
objects left to be permutated in possible ways. Thus we have number of ways to do so.
Exactly two objects are fixed: After fixing two objects in
ways, we have objects left to be permutated in possible ways. Thus we have number of ways to do so.
Exactly three objects are fixed: After fixing three objects in
ways, we have objects left to be permutated in possible ways. Thus we have number of ways to do so
... As all objects are fixed, we are left with only one way to accoplish that.
Therefore by principle of inclusion and exclusion, we can conclude that
Application: There is no magic trick that is solely based on the idea of derangement, but it appears everywhere in cards. For instance, let us say you and your friend each has a randomly-shuffled deck of cards. If you two compare the card one at a time and check if it is the same card, what is the probability that there is no match?
- This question is equivalent to asking "what is the probability of having a derangement for a permutation of length 52?" We can apply the equation to obtain the total number of derangement when
, and divide that by the number of total permutation when , we obtain . One interesting fact is that .