Mathematics

home 

 

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 (see note).

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:

 10! 10! 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
10_P_4 = ------- = ---- = --------------------------------------
 (10 - 4)! 6! 6 x 5 x 4 x 3 x 2 x 1

 = 10 x 9 x 8 x 7 = 5040
From this we can see that the more general formula for finding the number of permutations of size k taken from n objects is:

 n! 
n_P_k = -------- 
 (n - k)!
For our CAT example, we have:

 3! 3 x 2 x 1
 3_P_2 = ---- = ----------- = 6
 1! 1
We can use any one of the three letters in CAT as the first member of a permutation. There are three choices for the first letter: C, A, or T. After we've chosen one of these, only two choices remain for the second letter. To find the number of permutations we multiply: 3 x 2 = 6.

Note: What's a factorial? A factorial is written using an exclamation point - for example, 10 factorial is written 10! - and means multiply 10 times 9 times 8 times 7... all the way down to 1.

Combinations

When we want to find the number of combinations of size 2 without repeated letters that can be made from the three letters in the word CAT, order doesn't matter; AT is the same as TA. We can write out the three combinations of size two that can be taken from this set of size three:

We say '3 choose 2' and write 3_C_2. But now let's imagine that we have 10 letters from which we wish to choose 4. To calculate 10_C_4, which is 210, we don't want to have to write all the combinations out!

Since we already know that 10_P_4 = 5040, we can use this information to find 10_C_4. Let's think about how we got that answer of 5040. We found all the possible combinations of 4 that can be taken from 10 (10_C_4). Then we found all the ways that four letters in those groups of size 4 can be arranged: 4 x 3 x 2 x 1 = 4! = 24. Thus the total number of permutations of size 4 taken from a set of size 10 is equal to 4! times the total number of combinations of size 4 taken from a set of size 10: 10_P_4 = 4! x 10_C_4.

When we divide both sides of this equation by 4! we see that the total number of combinations of size 4 taken from a set of size 10 is equal to the number of permutations of size 4 taken from a set of size 10 divided by 4!. This makes it possible to write a formula for finding 10_C_4: 

 10_P_4 10! 10!
 10_C_4 = -------- = ------- = ----------
 4! 4! x 6! 4!(10-4)!


 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
 = --------------------------------------
 4 x 3 x 2 x 1 (6 x 5 x 4 x 3 x 2 x 1)


 10 x 9 x 8 x 7 5040
 = -------------- = ------ = 210
 4 x 3 x 2 x 1 24

More generally, the formula for finding the number of combinations of k objects you can choose from a set of n objects is:

 n!
n_C_k = ----------
 k!(n - k)!
For our CAT example, we do the following:

 3! 3 x 2 x 1 6 
3_C_2 = ------ = ----------- = --- = 3
 2!(1!) 2 x 1 (1) 2