Arrangements of Letters
Date: 09/14/1999 at 12:09:24 From: Kevin Subject: Combinatorics A problem has arisen in my review of combinatorics and discrete math. Any aid you can provide would be helpful. a. In how many ways can the letters in UNUNSUAL be arranged? (This is simply 8!, correct?) b. For the arrangements in part (a), how many have all three U's together? c. How many of the arrangements in part (a) have no consecutive U's? Once again, I thank you very much for your time.
Date: 09/14/1999 at 13:32:15 From: Doctor Mitteldorf Subject: Re: Combinatorics Dear Kevin, All these problems require some thought. They can't be done by plugging numbers into a formula. Even the part about arranging the letters of UNUNSUAL (should that be UNUSUAL?) requires thought, because the 8! assumes that all the letters are different. In other words, suppose you have 8 letters ABCDEFGH and you ask how many ways they can be arranged. 8! is certainly the right answer. But suppose now that the A and the B are identical - say they're both A's. Then, I would think, you've double counted the entire number of permutations. How do I know? Because each time you've come up with A in some slot and B in a later slot, you've also counted a permutation that had B where the A was and A where the B was. So the answer to this new problem is not 8! but half of 8! . Now suppose you had 3 letters that were the same, as in AAADEFGH. How many different permutations are there of these letters? I say that if your answer is 8! you've overcounted by a factor of 6. Why 6? Well, say one of the permutations in your list is A...B...C. There's another one that looks like B...A...C, and there are four more that look like A...C...B, C...B...A, C...A...B, and B...C...A. This 6 is actually the number of permutations of the 3 identical things - that's how much you overcounted by. So the answer for AAADEFGH is 8!/3! . To get the right answer in a statistics problem, you almost always have to do this kind of detailed thinking. Without it, you can never be confident in your answer. For part b: How many ways have all 3 U's together? Well, let's start with 3 U's followed by 4 different letters. The 4 different letters can be arranged in 4! different ways. Now suppose the 3 U's are all at the end. That's 4! more. Two more possibilities are X-UUU-XXX and XXX-UUU-X, where the X's stand for the letters NSAL. It looks as if the 4 extra letters can be ordered in 4! different ways, and the U's can be placed in and around them in 5 different ways, for a total of 5*4! (which is just 5!) possibilities. Try understanding these thoroughly, and doing some problems like them, before you move on to the other questions, which are harder yet. For example, let's take UNUNSUAL, the 8-letter word as you've written it. There are 3 U's and 2 N's in this version. How many different permutations of these 8 letters are there? - Doctor Mitteldorf, The Math Forum http://mathforum.org/dr.math/
Date: Date: 07/31/2002 at 07:34:02 From: Paul Subject: Combinatorics Hi, In looking at the answer to part (b), it occurs to me that it is possible to consider 'UUU' as a single letter, and then the problem turns into "How many different ways are there of ordering 5 different letters?", which gives you 5! directly. Regards, Paul
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.