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
We can also use Pascal's Triangle to find combinations:
Row 0 1
Row 1 1 1
Row 2 1 2 1
Row 3 1 3 3 1
Row 4 1 4 6 4 1
Row 5 1 5 10 10 5 1
Row 6 1 6 15 20 15 6 1
Pascal's Triangle continues on forever - it can have an infinite number of rows. Each number is the sum of the two numbers just above it. For the 1 at the beginning of each row, we imagine that Pascal's triangle is surrounded by zeros: to get the first 1 in any row except row 0, add a zero from the upper left to the 1 above and to the right. To get the 3 in row 4, add the 1 left and above to the 2 right and above.
To find the number of combinations of two objects that can be taken from a set of three objects, all we need to do is look at the second entry in row 3 (remember that the 1 at the top of the triangle is always counted as row zero and that a 1 on the lefthand side of the triangle is always counted as entry zero for that row).
Looking at the triangle, we see that the second entry in row 3 is 3, which is the same answer we got when we wrote down all the two-letter combinations for the letters in the word CAT.
Row 0 1
Row 1 1 1
Row 2 1 2 1
Row 3 1 3 3 1
Suppose we want to find 10_C_4? To use Pascal's Triangle we would need to write out 10 rows of the triangle. This is a good time to use a formula.
More generally, to find n_C_k ("n choose k"), just choose entry k in row n of Pascal's Triangle.
One of the hardest parts about doing problems that use permutations and combinations is deciding which formula to use.
From the Dr. Math archives:
Permutations and Combinations 
The Math Forum is a research and educational enterprise of the Drexel University School of Education.