**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

As a matter of fact, exactly the same analysis for

for the number of derangements of

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

second rows which agree with the first row in the chosen

The preceding calculation gives the answer for a fixed set of *t*positions. However, there are many ways of choosing a set of *t*positions 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 *t*from 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

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

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

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

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

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

Home | Publications | Preprints | MITACS | Poker Digest | Poker Computations | Feedback

website by the Centre for Systems Science

last updated 27 August 2001