Poker Digest Vol. 2, No. 16, July 30 - August 12, 1999
In the first part of this series, I developed the inclusion-exclusion formula via two examples. In the second part, the level of sophistication increased as we counted the number of derangements of 52 objects motivated by the claim that the odds of encountering two identical cards in the same two positions, when one deck of cards is laid out in a row of 52 cards in some fixed order while the other deck is randomly shuffled and laid out in a row of 52 cards beneath the first row, are better than 5:3.
Last year someone posed the following question on RGP (the newsgroup rec.gambling.poker): If one standard deck of 52 cards is spread out in a row in some fixed order and another standard deck of 52 cards is spread out in a row beneath, after having been randomly shuffled, what is the probability there are precisely t positions in which the two rows have identical cards? We easily see the previous article dealt with the case t = 0. So is this problem easier, harder or about the same difficulty?
Probably the best approach is to use what we already know. What do we
already know? Last time we saw the number of derangements of 52
objects is given by the formula
Thus, if we choose t positions and ask how many arrangements of
the second row agree precisely in these t positions with the first
row, we need the second row to not agree with the first row in all
of the remaining 52-t positions, that is, the second row needs to
be a derangement of the first row over the 52-t remaining positions.
By substituting 52-t in the formula above for the number of
derangements of n objects, we see there are
The preceding calculation gives the answer for a fixed set of tpositions. However, there are many ways of choosing a set of tpositions where the two rows may agree. Indeed, there are C(52,t)choices for the t positions where the two rows may agree since it
is defined to be the number of ways of choosing subsets of size tfrom a set with 52 members. Recall that
C(52,t) = 52!/t!(52-t)!.
We then multiply C(52,t) by the result above to obtain the number
of second rows agreeing with the first row in exactly t positions.
After performing the straightforward algebra, one obtains
There are a few situations for which the number may be calculated
directly and easily. Let's see how they agree with the formula
just derived. First, how many second rows can agree with the first
row in exactly 51 places? A little reflections yields that there
are no such second rows because if the second row agrees with the
first row in 51 places, then there is no choice for the last position
and they must agree there as well. Hence, the answer for t = 51is zero. If one plugs t = 51 into the formula, one obtains
Second, the number of second rows agreeing with the first row in
all 52 places is 1. Plugging t = 52 into the formula yields
Now let's directly calculate how many second rows agree with
the first row in exactly 50 places. There are
C(52,50) = 1,326ways to choose the positions where the rows agree. In the remaining
two positions they either agree or the elements are interchanged.
Therefore, there are 1,326 second rows agreeing with the first row
in exactly 50 positions. Now substituting 50 for t in the formula
Finally, let's finish with some probabilistic comments. As we observed in the last issue, the terms inside the parentheses in the final formula are the initial terms in the series expansion for 1/e. Moreover, the absolute value of the error in using 1/e as an approximation for this expression is less than 1/(52-t+1)! which is very small for all but large values of t. The bottom line is that 1/t!e is very close to the true probability of obtaining a second row which agrees with the first row in exactly t positions. (We define 0! to be equal to 1 which is a convenient convention in this problem.)