Take a deck of 52 cards and shuffle it well. What is the probability that at least one card will be in the same position as when you started? To answer that question, we first have to define derangements and subfactorials.
A derangement is a permutation of a set that leaves no element where it started. For example, the set {1, 2, 3} has two derangements: {2, 3, 1} and {3, 1, 2}. The arrangement {2, 1, 3}, for example, is not a derangement because it leave 3 in place. The number of derangements of a set with n elements is !n, the subfactorial of n. (Note that factorial puts the exclamation point after the number and subfactorial puts the exclamation point in front. This is unfortunate notation, but it’s commonly used.)
It turns out !n is given by
Note that the expression in parentheses is the power series for exp(-x) evaluated at x = 1 and truncated after the nth term. It follows that for positive n, you can calculate !n by first computing n!/e and rounding the result to the nearest integer.
If a permutation is randomly selected so that all permutations are equally likely, the probability that a permutation is a derangement is !n / n!. As n increases, this probability rapidly approaches 1/e. That means that for moderately large n, the probability that a random permutation will leave at least one element fixed is approximately 1 -1/e or about 63%. So there’s about a 63% chance that at least one of the cards is in the same position after shuffling the deck.
The approximation above says that !n / n! ≈ 1/e. How good is that approximation? The error is the error in truncating the series for exp(-x). This is an alternating series, so the absolute error is bounded by the first term left out. In other words, the error is less than 1/(n+1)!. So for n = 52, the error is on the order of 10-70. Even for n as small as 10, the error is on the order of 10-8.
This says that the probability that at least one card stays in its original position after the deck is shuffled hardly depends on the size of the deck. For example, if the deck had 20 cards or 100 cards rather than 52, the probability of at least one card being unmoved after the cards are shuffled would be essentially the same.
Extra credit
So far we only looked at the probability of no card staying in the same place (or the complementary probability, at least one card not staying in the same place.) What is the probability that exactly k cards stay in the same place after shuffling? This is given by
As n increases, this probability approaches 1/(k! e).
See Nonplussed! by Julian Havil for more details.
Related posts