For discrete math and probability students
Permutations
A permutation is a count of the unique orderings of distinct objects. The best way to understand it is to build the answer yourself.
Question: How many unique orderings can you make from 5 distinct objects, A, B, C, D and E?
Ask how many choices you have for the first spot: 5. Once that's chosen, how many for the second? 4, no matter which you picked first. So there are 5 × 4 = 20 ways to fill the first two spots. Keep going and you get 5 × 4 × 3 × 2 × 1 = 120. For n objects it's n × (n − 1) × (n − 2) × … × 2 × 1.
That product gets long, so we use factorial notation: n! means the product of the first n positive integers.
5! = 5 × 4 × 3 × 2 × 1 = 120
8! = 40,320
What if we want orderings of fewer objects, say 2 taken from 5? We already did that in the construction above: 5 × 4 = 20. As a compact formula:
nPr = n! / (n − r)!
5P2 = 5! / 3! = 5 × 4 = 20
Combinations
A combination is a permutation where order doesn't matter. Ask, "In how many ways can you select all 5 objects?" The answer is 1, because every ordering counts as the same selection.
Now ask, "How many ways can you select 2 objects from 5?" If order mattered, it would be 20. But two objects can be ordered 2 ways (A, B and B, A), and those now count as one, so we divide by 2 and get 10. In general, take nPr and divide by the number of ways to order r objects:
nCr = nPr / r! = n! / [(n − r)! × r!]
Try these
- Show that the formula for nCr gives 1 when you use it to answer "In how many ways can you select all 5 of 5 distinct objects?"
- How many unique orderings of the letters in MISSISSIPPI are there? This one isn't quite in the form we've prepared for, but you can figure it out. Hint: there are 11 letters, but not 11 distinct letters. Think about how to divide out the repeats.
Good luck! If you'd like to check your answers, email me at michael@expertmathtutor.net.