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

Brian Alspach

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

$\begin{displaymath}A-A(1)+A(2)-A(3)+\cdots+(-1)^iA(i)+\cdots,\end{displaymath}$

where A denotes the total number of objects in the set.

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 $f(j)\neq j$ 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

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

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

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

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!/e. Therefore, the probability of obtaining a derangement is essentially 1/e which essentially equals 0.3679. The probability of not getting a derangement is 0.6321. Thus, the odds of not getting a derangement is 0.6321:0.3679 which is slightly more than 5:3 as claimed by Ortiz.''

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