Combinations of the Letters in a Name

Date: 03/04/98 at 14:52:07
From: Sara
Subject: A formula for the number of combinations of rearranging a 
name

Hi, 

You seem to know a lot about mathematics so I was wondering if you 
could answer this. My name is SARA, and there are a number of ways of 
rearranging the letters of my name:

    SARA
    SRAA
    SAAR
    AARS
    AASR
    ASRA
    ARSA
    ARAS
    ASAR
    RASA
    RSAA
    RAAS

As you can see, there are 12 combinations; but if my name were JOEY, 
then the number of combinations is 24 -- double the amount for Sara -- 
because Sara has 2 A's.

Do you know a formula or how to work out a formula so that I can use 
it to work out the number of combinations for any name whatever the 
amount of letters or however many times a letter is repeated? If you 
can help me please email me back.

Thank you very much for your time!

Sara

Date: 03/04/98 at 16:12:05
From: Doctor Daniel
Subject: Re: A formula for the number of combinations of rearranging a 
name

Hi Sara,

You asked a great question about combinations!

Let's pretend that, given an n-letter name, all of the letters were 
actually different. For example, suppose the name is

    NATHAN

Maybe think of the N's as N1 and N2, and similarly with the A's, so 
it was something like N1-A1-T-H-A2-N2. Is that clear?

Then it is very easy to convince yourself that there'd be

   n * (n-1) * (n-2) * ... * 1
   
combinations of the letters. This product comes up so often that it's 
got a name, factorial, and a notation, n! (with the exclamation 
point). I'll use that notation a lot.  

Anyhow, why is the number of combinations equal to n! when the letters 
are distinct? Easy: there are n possible letters for the first slot, 
then only n-1 left for the second slot, and so on, down to the last 
letter, where you only have one choice.

So, for example, if you start with 6 letters, all different, there are
720 rearrangements, since 6! = 6*5*4*3*2*1 = 720.

Now, how to deal with those pesky double (and triple and ...) letters? 
I'll give two answers, and you can pick your own favorite:

    1) (My favorite) It's also not at all hard to convince yourself   
       that, if I give you k letter A's (say, if k=3, A1, A2, and A3),   
       that there are k! different ways of arranging them.  Of course,   
       it's exactly the same as above. But what if I told you that I 
       only cared about the cases where A1 came before A2 and A3, and 
       A2 came before A3? Then there's only 1.

       Let's use the same idea on the name rearrangement example:
       suppose the name was your name, S-A1-R-A2. There's 24 = (4!)
       combinations of these four letters, with the two A's being
       different, as you know. But in exactly half of them, the A1
       comes before the A2. So keep these, and throw out the others.
       You threw out half of them, so that leaves you with 12 = 4!/2!
       remaining.

       This strategy works in general ... Take my aunt ELLEN; the 
       letters in her name can be made into 5! = 120 arrangements, of
       which 60 have the E1 before the E2, and of those, 30 have the
       L1 before the L2. So there are 30 = 120/(2!*2!) ways to
       rearrange her name.

    2) The other way: suppose I show you any rearrangement of ELLEN:

           N-L-L-E-E.

       Then, when I separate the identical letters, there are exactly

           4 = 2! x 2! combinations that have that order: 
        
           N-L1-L2-E1-E2, N-L2-L1-E1-E2, 
           N-L2-L1-E2-E1, N-L1-L2-E2-E1.  

       So for every example in the set I want to count, there are 4 
       examples in the bigger set I know how to count easily (since I
       know from before that it has n! elements). That gives the same
       answer.

So the ultimate formula is this: suppose I give you a name with n 
letters, and there are k1 of one letter, k2 of another letter, and so 
on, up to kz. For example, in ELLEN,

    n = 5, k1 = 2 [two E's], k2 = 2 [two L's], k3 = 1 [one N]).  

Then the number of rearrangements is n!/k1!k2!...kz!

I hope this helps!

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