Skip to main content

IBM Systems  >   z Systems  >   z/VM  >  

There's a well-known combinatorics problem that goes like this. Suppose N men throw their hats into a closet and later extract them blindly -- one hat per man, uniform probability that any particular hat will go to any particular man. What is the probability that none of the men will wind up with their own hat? This is sometimes known as the hat-check problem -- the men check their hats at a restaurant and then the tickets get scrambled. On an electronic bulletin board which I follow, almost the same problem popped up:

Three chips are selected from each of 10 different batches. The chips are numbered 1 thru 10 according to the batch they were selected from. There are 10 bins numbered 1 thru 10 each capable of holding 3 chips. The chips are randomly distributed across bins. What are the odds that no chip will end up in the bin with the same number as the chip?

An approximate solution is 1/e**3. This comes from the principle of inclusion and exclusion, doing the hat-check problem three times. The solution to the hat-check problem is to count all the ways that the men might get their hats back, subtract all the ways in which they could get their hats back and at least one of the men get his own hat, add back the number of ways at least two could get their own hats (because you counted these twice when subtracting the at-least-one cases), subtract the ways at least three... With 10 men checking their hats, the number of ways they can each wind up with someone else's hat is

 
  10! - 10*9! + 10*9*8!/2! - 10*9*8*7!/3! + ... + 1
 
 = 10!( 1/0! - 1/1! + 1/2! - 1/3! + 1/4! - 1/5! + ... + 1/10!)
The term in parenthesis is a truncation of the expansion for 1/e. So the probability that nobody gets their own hat back in the 10 men, one hat apiece problem is approximately 1/e. I've breezed through this solution just to get on to the 10 men, 3 hats apiece problem. Most any introductory combinatorics book will have more detail. The one I have most used is Introduction to Combinatorial Mathematics by C. L. Liu. (McGraw Hill, 1968.)

To solve the 10 men, 3 hats apiece problem, just run the hat-check problem three times, right? Well, not quite, although that is a decent approximation. The best way I've found to see the difference is to look at the very simple 2 men, 2 hats apiece case. If two men throw one hat apiece into each of two closets, there are only four ways to get the hats back. But if all four hats go into one closet, there are 24 ways (ordered -- 6 unordered) to get the hats back, only four (one, unordered) of which results in neither man having either of his own hats.

The "chips in bins" problem gave me incentive to read "The Rook Polynomials" section of Liu's book, pages 111-118. A rook polynomial is an ordinary generating function for the number of ways n non-taking rooks can be placed on a given chessboard. A placement of rooks is non-taking if none of the rooks can take another moving in the usual chess sense, i.e. none are in the same row or column. If I counted right, the rook polynomial for a 3x3 chessboard is

                        2     3
            1 + 9x + 18x  + 6x
which means that there is one way to place zero non-taking rooks on a 3x3 chessboard, 9 ways to place one, 18 ways to place two, and 6 ways to place three non-taking rooks. And 0 ways to place 4 or more. Permutations can be counted by placing n non-taking rooks on an nxn chessboard -- a rook in the ith row and jth column indicates that the ith object is put into the jth box. The hat problem is the same, except now your chessboard has forbidden squares, specifically the squares on the main diagonal. The problem in this representation is to place 30 non-taking rooks on a 30x30 chessboard, with the 10 3x3 squares on the main diagonal forbidden. A rook on the ith row and jth column indicates that the ith hat goes to the int((j-1)/3)+1th man. (A minor complication: elements 1-3, 4-6, ..., 28-30 are indistinguishable. So we have to divide our counts by (3!)**10.)

To make the next logical leap, you probably need to look at a reference like Liu; I don't want to write 8 pages here! Anyway, to count the number of ways to place non-taking rooks on the 30x30 chessboard with the 3x3 squares deleted, use the principle of inclusion/exclusion and the rook polynomial for the forbidden region. The forbidden region is 10 disjoint copies of a 3x3 chessboard, so the rook polynomial is

                               30
                              ----
              2     3  10     \       i
( 1 + 9x + 18x  + 6x  )    =   \   k x                       (*)
                               /    i
                              /
                              ----
                               i=0
So the number of ways of distributing the 30 objects, 3 of each kind, into the 10 cells so that each cell has 3 objects and no object is in the cell of the same number as the object, is
                 30
                ----
           1    \        i
    N  = -----   \   (-1) k (30-i)!
             10  /         i
         (3!)   /
                ----
                 i=0
 
where the k  come from (*).
           i
The number of ways to distribute the objects if no cells are forbidden is
         30!
    M = -----
            10
        (3!)
and so the desired probability is N/M. To give you some confidence in this method, notice that in the one hat per person problem with 30 people, the rook polynomial of the forbidden region would be
            30
   ( 1 + x )
and the answer reduces then to the known solution of approximately 1/e.

Mathematically, the problem is completely solved at this point, but I wondered if someone would come along, do the calculations, and show that my analysis gave a probability greater than one. So rather than saying "Computation is left to the reader", I wrote a REXX program to raise a polynomial to an integer power and do the other calculations. The program is available in my SPITABCD package, available in the VM Download Library. I calculated the desired probability N/M = 0.044793563748... This compares with 1/e**3 = 0.04978706..., which is not really as close as I might have thought. Maybe 10 isn't all that big? Varying the NUMERIC DIGITS parameter in my REXX program didn't change the answer except in the "pretty insignificant" digits; I found NUMERIC DIGITS 15 was adequate to get integers for the coefficients of the 30th degree rook polynomial.

I'm not much interested in cards, but I've recently learned of a similar problem and solution in figuring odds in Frustration Solitaire.


Return to the author's home page.