Tuesday, April 10, 2007

Permutations

Suppose we want to find the number of ways to arrange the three letters in the word CAT in different two-letter groups where CA is different from AC and there are no repeated letters.
Because order matters, we're finding the number of permutations of size 2 that can be taken from a set of size 3. This is often written 3_P_2. We can list them as:
CA CT AC AT TC TA
Now let's suppose we have 10 letters and want to make groupings of 4 letters. It's harder to list all those permutations. To find the number of four-letter permutations that we can make from 10 letters without repeated letters (10_P_4), we'd like to have a formula because there are 5040 such permutations and we don't want to write them all out!
For four-letter permutations, there are 10 possibilities for the first letter, 9 for the second, 8 for the third, and 7 for the last letter. We can find the total number of different four-letter permutations by multiplying 10 x 9 x 8 x 7 = 5040. This is part of a factorial.
To arrive at 10 x 9 x 8 x 7, we need to divide 10 factorial (10 because there are ten objects) by (10-4) factorial (subtracting from the total number of objects from which we're choosing the number of objects in each permutation). You can see below that we can divide the numerator by 6 x 5 x 4 x 3 x 2 x 1

Foot note
http://mathforum.org/dr.math/faq/faq.comb.perm.html

No comments: