Counting Possible Letter ArrangementsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/