Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search