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