Permutations

Permutations

A permutation is an arrangement of objects without repetition where order is important.

Permutations using all the objects

A permutation of n objects, arranged into one group of size n, without repetition, and order being important is:

   nPn = P(n,n) = n!

Example: Find all permutations of the letters "ABC"

   ABC  ACB  BAC  BCA  CAB  CBA

Permutations of some of the objects

A permutation of n objects, arranged in groups of size r, without repetition, and order being important is:

   nPr = P(n,r) = n! / (n-r)!

Example: Find all two-letter permutations of the letters "ABC"

   AB  AC  BA  BC  CA  CB

Shortcut formula for finding a permutation

Assuming that you start a n and count down to 1 in your factorials ...
P(n,r) = first r factors of n factorial

Distinguishable Permutations

Sometimes letters are repeated and all of the permutations aren't distinguishable from each other.
Example: Find all permutations of the letters "BOB"
To help you distinguish, I'll write the second "B" as "b"

   BOb  BbO  OBb  ObB  bBO  bOB

If you just write "B" as "B", however ...

   BOB  BBO  OBB  OBB  BBO  BBO

There are really only three distinguishable permutations here.

   BOB  BBO  OBB

If a word has N letters, k of which are unique, and you let n (n1, n2, n3, ..., nk) be the frequency of each of the k letters, then the total number of distinguishable permutations is given by:

Consider the word "STATISTICS":
Here are the frequency of each letter: S=3, T=3, A=1, I=2, C=1, there are 10 letters total

                    10!        10*9*8*7*6*5*4*3*2*1
Permutations = -------------- = -------------------- = 50400
              3! 3! 1! 2! 1!    6 * 6 * 1 * 2 * 1