Counting Possible Letter Arrangements

Date: 10/25/2004 at 22:39:25
From: patrick
Subject: counting - permutations

I'm a mathematics teacher and my class was working on this problem:

In the word GUMTREE, how many ways can the letter M be to the left of
the two E's?

I got the answer using cases, which I think you'll agree is long and
tedious.  The students wanted to know a shorter way of doing it.

So I used the idea that if I just wanted the M to be to the left of
the G then it must occur in 1/2 of all the possible occurences without
restriction.  So I was reasoning that with the M, E, and E we get x E
x E x where the x represents the possible positions of the M.  The
answer would be 1/3 of the total.

Even though that answer fits the cases method, I'm wondering if it is
a fluke?

Date: 11/03/2004 at 12:49:15
From: Doctor Douglas
Subject: Re: counting - permutations

Hi Patrick.

I don't believe that it is a fluke.  Consider that all permutations
must include the M, E, and E somewhere.  Hence reading left-to-right,
these must either be *M*E*E*, *E*M*E*, or *E*E*M*, where the stars
indicate the possible presence of other letters.  Of these three 
patterns, exactly one-third of them fit your desired rule (M<E,E), so 
the one-third rule describes the number of valid permutations.

Let's try a slightly harder problem to verify this:  all of the 
possible permuations of SNAP, with S left of N and A left of P:

   # of total permutations = 4! = 24.

   S-left-of-N (S<N) is a 50% restriction, so we are down to 24/2
     = 12 permutations, for which the pattern is *S*N*.

   A-left-of-P (A<P) is an independent 50% restriction, and we
     are left with 12/2 = 6 permutations.

These six permutations are easily found as SNAP, SANP, SAPN, ASNP, 
ASPN, ANSP.

What happens if the restrictions aren't independent?  Let's try to 
enumerate the permutations of SNAP with S<P and N<P:

   # of total permutations = 4! = 24.

   S<P is a 50% restriction, so we are down to 24/2 = 12.

   N<P is trickier. It is not a 50% restriction because the situation
     after enforcing S<P is now {*S*P*}.  The N must go in one of
     these three star spots, of which two (*N*S*P*, *S*N*P*) fit 
     the condition and one (*S*P*N*) does not, so our count should be  
     (2/3) x 12 = 8.

And we find eight permutations that work:  SNAP, ASNP, SANP, SNPA, 
NSAP, ANSP, NASP, NSPA.

So this process does work for a constraint that is slightly more 
complicated.  Eventually we can make constraints so complicated that
following these rules is only slightly better than enumerating by 
cases [e.g. permutations of "GUMTREE", with G<M, unless (T>R>E or
T>E>E>R)].

I hope that this helps, and gives you a method for handling things 
when you want to count permutations with simple constraints.

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/