Mathematica Pearls:
Problems and Solutions

Studying permutations with Mathematica

Edited by Don Piele

Complete permutations (sometimes called derangements) are permutations 
that leave no number fixed. For example, (3,1,2} and {2,3,1} are the only 
complete permutations in the set of six permutations of {1,2,3}. 
Thus if three people check their hats and the 
hats are somehow scrambled, the probability that none of the three get 
their own hat back is 2/6 or 1/3. It is a surprising result, that as the 
number of hats grows, the probability that no one gets their own hat back 
approaches 1/E (See Introduction to Probability Theory with Computing, by 
J. Laurie Snell, Prentice Hall, 1975.) Thus the number of complete 
permutations is closely approximated by n!/E.

Snell also shows that the number of complete permutations (cp) can be 
computed recursively as :

cp[1]=0;
cp[2]=1;
cp[n_]:= cp[n]= (n-1) cp[n-1] + (n-1) cp[n-2]

Snell argues: " Assume we want to find the number of ways n people can 
have hats none of which are their own. Assume one person, say Ann,  
arrives withher own hat, and all the the other n-1 people have different hats. 
Then Ann can change her hat with any one of the n-1 people, and then eveyone 
will not have have their own hat. There are cp(n-1) ways that the n-1 
people can have different hats, and Ann has n-1 people she can exchange 
with. Thus there are (n-1) cp[n-1] ways this can be done. However, there 
are other possibilities. One of the group of n-1 people could have their 
own hat, and the remaining n-2 have all different hats. Thus Ann need 
only exchange hats with the person who has their own hat and everyone 
will now have different hats. This can occur in (n-1) cp[n-2] ways. There 
is no duplication in these two ways that Ann can give up her hat, since 
if we undo the process, in one case we end up with only 1 person having 
their own hat and in the other case 2. These are the only two ways that 
Ann can give up her hat; hence the recursion relationship is proved."

Comparing this exact result to Round[ n!/E], we have total agreement for 
all n.

Table[{cp[i],Round[N[i!/E]]},{i,1,12}]//MatrixForm

Other problems can also be looked at with the aid of complete permutations.

Menage II  (Source:  Problems and Snapshots from the World of 
Probability, Gunnar Blom, Springer-Verlag 1991)

At a dinner for 4n people (all husband and wife pairs) , the host assigns 
at random 4 people to sit at each of the n tables, with the restriction 
that each table should have two men and two women.This is done by 
allowing the women to be seated first, two to a table, and randomly 
placing the men in the empty seats. Find the probability that none of the 
married couples is sitting at the same table.

One way to model this problem is to number the tables from 1 to n, and if 
a women is placed at table i then make out a slip for her husband with 
her table number on it. Thus the men will all end up with slips numbered 
{ 1, 1, 2, 2, 3, 3, .... n, n}. If a husband with slip 1 sits at table 1 
he will be sitting with his wife. Any complete permutation of the slip 
numbers will result in a seating where no husband sits with his own wife.

Your Turn

a) Generate the complete permutations of {1,1,2,2,3,3,....,n,n} for as 
large an n 
    as possible.
    
b) Is there a  way of counting the complete permutations of 
{1,1,2,2,3,3,...n,n}
    without generating them?
     
c) The number of different ways of seating the men is (2n)!/ (2 ^n). Thus 
the probability that none end up sitting with his own wife is: 

            number of  complete permutations  of {1,1,2,2,3,3,4,4,....n,n}
p[n] =    
-------------------
                                  (2n)!/ (2 ^n)   
         
         Evaluate p[n]  for a few values of n.                         

 d) Does the Limit[p[n], n-> Infinity] exist?

SUBMITTING PROBLEMS AND SOLUTIONS

The preferred way to submit problems or solutions is via email. They may also be submitted on paper or on a disk through the regular mail. When you submit your work, include a brief English description of your solution or use comments in your program to help the reader follow your ideas. Of course, you should include your name, institution, category (high school, college undergraduate, other) and mail or email address.

CONTACTING THE EDITOR

Donald T. Peile
Mathematics Department
University of Wisconsin-Parkside
900 Wood Road
Kenosha, WI 53141
peile@cs.uwp.edu
fax: 414-595-2056

ELECTRONIC SUBSCRIPTIONS

Included in the distribution for each electronic subscription is the file Perm.ma containing Mathematica code for the material described in this article.