**Poker Digest Vol. 2, No. 15, 16 - 29, 1999**

``Bib'', I said, looking the crafty old poker-master in the eye, ``Let me
now show you a nice application of the *Principle of Inclusion-Exclusion*.
Perhaps you recall recently seeing a short item in the *Globe and Mail*
which read as follows. `Run out of cash at the bar?...Get your friend
to pay,' writes Greg Gutfeld in *Men's Health*. `Have him shuffle
two decks
and place them side by side. Explain that you will simultaneously deal
cards face-up from both decks. Bet even money that in the course of dealing,
you'll simultaneously turn over two identical cards. If the two aces of
spades show up at the same time, you win. If you go through the decks
without hitting one identical pair, your pal wins.'''

``To most people, two
cards in the same position in two randomly shuffled decks seems very
unlikely,'' says Darwin Ortiz, author of *Gambling Scares*. ``But
the odds are better than 5-to-3 in your favor.''

I was not at all surprised to learn he had seen the article and is a *Globe and Mail* reader. I've watched the old fox pluck a few chickens at
the tables and know he fools many people with that sleepy demeanor.

``Alright, Bib, let me remind you that if we have some objects endowed
with certain properties, we let *A*(*i*) denote the number of objects having
*i* or more properties. We compute *A*(*i*) by taking each subset of *i*properties and make the easy computation of the number of objects having
that subset of properties (and possibly more) and sum all these numbers.
The Principle of Inclusion-Exclusion states that the number of objects
having none of the properties is given by

where

Let's interpret the example in the article in the appropriate context.
Write down the numbers 1,2,3,...,52 in a row in that order. Now take
a random permutation of 1 through 52 and write it in the row below. An
equivalent question is what are the odds of having two identical numbers
in the same position in the two rows? A permutation which has no
positions in which it agrees with the first row is called a *derangement*
by mathematicians. Thus, Ortiz is claiming the odds of NOT getting a
derangement, that is, at least one position where the two rows agree, are
better than 5-to-3. Is this OK, Bib?''

``Yeah, I follow so far.''

``What I want to do is count the number of derangements of 52 objects. Counting derangements is a classical application of the Principle of Inclusion-Exclusion and appears in any text book which discusses the Principle of Inclusion-Exclusion. First, recall that the number of permutation of n objects is n!; a simple enough result. Unfortunately, these numbers grow very quickly and produce mind boggling strings of digits.

Recall that we can think of a permutation of 1,2,...,52 as a function
*f* where *f*(*j*) denotes the number in position *j* of the permutation.
Then a derangement is a permutation *f* for which
always
holds. We shall say a permutation *f* has property *P*_{j} if *f*(*j*)=*j*.
Thus, a permutation is a derangement precisely when it satisfies none
of the properties. Isn't this beginning to sound like the simple
examples we did in the previous article?''

In his usual perceptive way, Bib thought for a few minutes and said,
``Yeah, I see that we are looking for the permutations with none of
the properties, but the key is calculating the values of *A*(*i*) in the
Inclusion-Exclusion formula.''

``Bib, you have hit the nail on the head. The one other ingredient we
need in order to be able to apply the Inclusion-Exclusion formula is for
the numbers *A*(*i*)to be easy to calculate as *i* goes from 1 through 52. So think about
this for a moment. If I choose a fixed set of *i* properties, then how
many permutations satisfy the set of *i* properties remembering they
can satisfy additional properties as well?''

``Well,'' he started, ``If a permutation has that set of properties, then
*f*(*j*)=*j* for each *P*_{j} in the set of properties, but it can do anything
on the remaining *n*-*i* elements. I guess that means there are (*n*-*i*)!such permutations.''

``Bib, it is so beautiful to watch you make these step-by-step
deductions. You are correct and this means to get *A*(*i*) we multiply
(*n*-*i*)! by the total number of ways of choosing a set of *i* properties
from 52 possible properties. This is simply C(52,i). Thus,
*A*(*i*) =
52!/*i*!. We substitute into the Inclusion-Exclusion formula to find the
number of derangements is given by

The exact evaluation of the preceding formula leads to a messy calculation
involving obscenely large numbers. As it turns out, we may avoid the
exact evaluation because there is a simple way to obtain a good approximation
but it requires some mathematics typically found in a calculus course.
Factor 52! out of the preceding formula which produces

The expression in the parentheses is the first 53 terms of the infinite series expansion of 1/e, where e is the base of the natural logarithms. Furthermore, the error obtained by using this approximation for 1/e is less than the absolute value of the next term, namely, 1/53!. The latter number is very close to zero meaning the expression in parentheses is very close to 1/e. This means the number of derangements of a 52-card deck is essentially 52!/

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

website by the Centre for Systems Science

last updated 27 August 2001