Permutations

The number of ways you can change the order of a set of things is called the number of PERMUTATIONS of that set of things. For example, how many different ways can you arrange the letters in the word

WHO
Answer: WHO    WOH    HWO    HOW    OHW    OWH = 6 ways
         1      2      3      4      5      6
Each different letter arrangement is called a permutation of the word "WHO". How about the word "STOP"? Well, here they are:

   STOP     STPO     SOTP     SOTP     SPTO     SPOT   <- starts with "S"
   TSOP     TSPO     TOSP     TOPS     TPSO     TPOS   <- starts with "T"
   OSTP     OSPT     OTSP     OTPS     OPST     OPTS   <- starts with "O"
   PSTO     PSOT     PTSO     PTOS     POST     POTS   <- starts with "P"
There are 24 ways to order the letters in "STOP". Is there a general rule here? Fortunately, yes. Here's the rule for "STOP":
  1. There are 4 ways to pick the first letter.
  2. After you pick the first letter there are 3 ways to pick the second letter.
  3. After you pick the first 2 letters, there are 2 ways to pick the third letter.
  4. After picking the first 3 letters, there is only 1 letter left to pick.
So the number of ways to order the letters in "STOP" is 4 x 3 x 2 x 1 = 24 ways!

FACTORIALS
When you multiply a whole number by all the whole numbers below it, that is called the FACTORIAL of that number. Factorials are used to compute permutations. In the previous example, we saw that 4 letters could be permuted 4 x 3 x 2 x 1 ways , or 24 ways. Six things can be permuted 6 x 5 x 4 x 3 x 2 x 1 ways or 720 ways. We write it in shorthand with an exclamation point, like this: 6! You can see from the table below that factorials get very large in a hurry:
  1!  =                                   = 1
  2!  =                             2 x 1 = 2
  3!  =                         3 x 2 x 1 = 6
  4!  =                     4 x 3 x 2 x 1 = 24
  5!  =                 5 x 4 x 3 x 2 x 1 = 120
  6!  =             6 x 5 x 4 x 3 x 2 x 1 = 720
  7!  =         7 x 6 x 5 x 4 x 3 x 2 x 1 = 5,040
  8!  =     8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320
  9!  = 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362,880
The number of permutations of n things is
n!

There is one more thing to know about factorials. When you divide one factorial by another, then a lot of the numbers on the low end cancel out. For instance:
        12!   12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
        --  = ------------------------------------------------ = 12 x 11
        10!             10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
REPEATED LETTERS
There is a special case when the things you are ordering are not all different. This is the case when you are permuting the letters in the word "MOON". 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 is :