I'm In ... No, I'm Out: Part III

Brian Alspach

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

$\begin{displaymath}52!-\frac{52!}{1!}+\frac{52!}{2!}- \frac{52!}{3!}+\cdots +\frac{(-1)^k52!}{k!}+\cdot +\frac{52!}{52!}.\end{displaymath}$

As a matter of fact, exactly the same analysis for n objects instead of 52 leads directly to the formula

$\begin{displaymath}n!-\frac{n!}{1!}+\frac {n!}{2!}- \frac{n!}{3!}+\cdots +\frac{(-1)^kn!}{k!}+\cdots +\frac{n!}{n!}\end{displaymath}$

for the number of derangements of n objects.

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

$\begin{displaymath}(52-t)!-\frac{(52-t)!} {1!}+\frac{(52-t)!}{2!}+\cdots+\frac{(-1)^k(52-t)!} {k!}+\cdots+\frac{(-1)^{52-t}(52-t)!}{(52-t)!}\end{displaymath}$

second rows which agree with the first row in the chosen t positions and nowhere else.

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

$\begin{displaymath}\frac{52!}{t!}(1-1+\frac{1}{2!}-\frac{1}{3!}+\cdots+\frac{(-1)^k} {k!}+\cdots+\frac{(-1)^{52-t}}{(52-t)!})\end{displaymath}$

as the number of second rows which agree with the first row in exactly t positions.

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

$\begin{displaymath}\frac{52!}{51!}(1 - 1) = 0\end{displaymath}$

as we should.

Second, the number of second rows agreeing with the first row in all 52 places is 1. Plugging t = 52 into the formula yields

$\begin{displaymath}\frac{52!}{52!}(1) = 1\end{displaymath}$

as it should.

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 yields

$\begin{displaymath}52\cdot 51(1 - 1 +\frac{1}{2}) = 1,326\end{displaymath}$

as expected.

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.)

website by the Centre for Systems Science
last updated 27 August 2001