Notes on Permutations

Permutations - Repeated Letters

There is a special case when the things you are ordering are not all different. For example when you are permuting the letters in the word "MOON" which has 2 of the letter O. Here are the permutations:


    MOON     MONO     MNOO
    OMON     OMNO     OOMN
    OONM     ONMO     ONOM
    NOOM     NOMO     NMOO

Why are there only 12, instead of 4 x 3 x 2 x 1 = 24 ways? Because you can't tell the O's apart, so their order doesn't matter. Suppose one of the O's was capital and the other one was small. Then you would have "MOoN" and "MoON". But our O's are alike and we can't tell the difference so we have "MOON" and "MOON", which are the same. We count them once. Since there are 2 "O"s, there are 2! = 2 x 1 = 2 ways of ordering them.

So the number of permutations of letters in the word MOON is:

    4!    4 x 3 x 2 x 1
   --- = --------------- = 4 x 3 = 12 ways
    2!            2 x 1

For the word "SASS", there are 4 letters and 3 "S"s so there are:

    4! =  4 x 3 x 2 x 1
   ---   --------------- = 4 ways of permuting the letters 
    3!        3 x 2 x 1     ( = SASS  SSSA  ASSS SSAS)

The number of permutations of n things
where r of them are the same

==>

n!
r!

Suppose there is a word with more than 1 letter repeated, like NOON? How do we compute the number of permutations of the letters in the word NOON? Well, you just divide by the number of permutations of this second letter also, like this:

Permutations of the letters in "NOON":

4! = 24 = 6
2! x 2! 4

You can list them out:
NOON NNOO NONO
ONNO ONON OONN

Here's the rule:

The number of permutations of n things
where 2 different elements are repeated (r₁ and r₂)

==>

n!
r₁! x r₂!

In our example of NOON, r₁ are the repeated Ns and r₂ are the repeated Os.