Players A and B each have a well shuffled standard pack of cards, with no jokers. The players deal their cards one at a time, from the top of the deck, checking for an exact match. Player A wins if, once the packs are fully dealt, no matches are found. Player B wins if at least one match occurs. What is the probability that player A wins?
Since player A is dealing from a shuffled (randomized) pack, the probability that A wins is independent of the order in which B's cards are dealt. So, without loss of generality, we can assume B's cards are dealt in order: 1, 2, 3, ... , 52. Therefore the probability that player A wins is the fraction of permutations of (a1, a2, ... , a52) for which ai i, for all i from 1 to 52. Such permutations are known as derangements.
Let d(n) be the number of derangements of n elements. Then, by the Inclusion-Exclusion Principle,
|d(n) =||(total number of ways to deal n cards)|
|− sum over i (number of deals for which ai = i)|
|+ sum over distinct i, j (number of deals for which ai = i and aj = j)|
|− sum over distinct i, j, k (number of deals for which ai = i, aj = j and ak = k)|
|± number of ways in which ai = i, for all i from 1 to n|
|(with the final sign dependent on the parity of n)|
Here, we start with n! deals, subtract those with one matching card, then add back the number with two matching cards (we just counted these combinations twice), and so on.
|So d(n)||= n! − nC1 · (n−1)! + nC2 · (n−2)! + ... ± nCn · (n−n)!|
|= n! − n!/1! + n!/2! + ... ± (−1)n|
Therefore, the probability that A wins is d(52) / 52! = 1 − 1/1! + 1/2! − 1/3! + ... + 1/52!
Note that this expression is the first 53 terms of the Maclaurin series for e−1. The series converges very rapidly to 1/e; the above probability is within 1/53! 2.34×10−70 of 1/e. Therefore, somewhat surprisingly, for any reasonably large number of cards, say, 10 or more, the probability that A wins is almost independent of the number of cards in the decks.