Permutations & Combinations
Audience: Discrete Math, Probability
|
|
Permutations: Simply put a permutation is the number of unique orderings of n (n is a positive integer) distinct objects.
The best way to understand permutations is to build an understanding through constructing the answer to a simple question.
Question: Suppose you have 5 distinct objects. How many unique orderings can be made from 5 distinct objects?
Let A, B, C, D, and E represent the 5 distinct objects.
We ask ourselves "how many choices do I have for the first object in the ordering"? The answer is 5. We can choose A or B or C or D or E for the first object. Now that we've chosen the first object, we ask "how many choices do I have for the second object?" Since we've already chosen the first object, there are 4 objects left to choose from for the second object. Notice that no matter which object we choose for the first object there are 4 objects left to choose from for the second object (e.g. choose A as the first object and we can choose from B or C or D or E for the second object OR choose B for the first object and we can choose from A or C or D or E for the second object OR etc.). You should now see that we have 5 choices for the first object and 4 choices for the second object. Since for each possible choice of the first object (5 in all) we have 4 possible choices for the second object, there are 5 * 4 = 20 choices for the first 2 objects in the ordering. Using this same line of reasoning for the number of choices for the 3rd, 4th, and 5th objects we see the total number of unique ordering of 5 distinct objects is 5 * 4 * 3 * 2 * 1 = 120. In the general case there are n * (n - 1) * (n-2) * ... * 3 * 2 * 1 unique orderings of n distinct objects.
If n is a big number, that's a lot of multiplying! It would be useful to have some kind of notation to represent these products of many factors. A special notation already exists to represent the product of the first n positive integers - its factorial notation. The symbol used to represent factorial is the exclamation point (!) - some examples follow:
5! = 5 * 4 * 3 * 2 * 1 = 120
8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40320
n! = n * (n - 1) * (n-2) * ... * 3 * 2 * 1
Now that we know there are n! unique ways to order n distinct objects, let's ask how many unique orderings there are of less than n distinct objects taken from n distinct objects. Let's look at a specific case and then we'll generalize.
Suppose we want to compute the number of unique orderings of 2 distinct objects taken from 5 distinct objects. This should be easy because we've already done this when we constructed the answer to the question "Suppose you have 5 distinct objects. How many unique orderings can be made from 5 distinct objects?" In that construction we had 5 choices for the first object and 4 choices for the second object. As above this means there are 5 * 4 = 20 unique ways to order 2 distinct objects taken from 5 distinct objects. Now we just need a compact formula to apply whenever the need arises.
We use "5P2" read 5 permute 2. 5P2 = 5! / (5 - 2)! = 5! / 3! = 5 * 4 * 3! / 3! = 5 * 4 = 20.
In the general case nPr = n! / (n - r)!
So what are combinations and how do they differ from permutations?
A combination can be thought of as a permutation where order does not make a difference. Recall the question posed above - we'll reword the question so that the solution is a combination - "Suppose you have 5 distinct objects. How many ways can you select all 5 objects?" The answer to this question should be intuitive and clear - the answer is 1. There's only one way to select all 5 objects taken from 5 distinct objects (remember order does not make a difference so all unique orderings are considered identical). No revelation there. Now consider the question where the answer was 20. I'll reword the question so the solution is a combination - How many ways can you select 2 objects from 5 distinct objects? We already know from the work done above that there are 20 ways to select 2 objects from 5 distinct objects if order makes a difference. So what about when order doesn't make a difference? Since we're taking 2 objects and 2 objects can only be ordered in 2 ways (A, B & B, A), we divide 20 by 2 and get 10. There are 10 ways to select 2 objects from 5 distinct objects (order of selection makes no difference). So, in general if we ask how many ways can we take r objects from n distinct objects the answer is nPr divided by the number of ways we can order r objects or nPr / r! = n! / [(n - r)! * r!] = nCr
Now that we know how permutations and combinations work and are familiar with factorials I'll ask a couple of questions.
-
Show that the formula for nCr = n! / [(n - r)! * r!] is equal to 1 when you use it to answer the question "Suppose you have 5 distinct objects. How many ways can you select all 5 objects?"
-
How many unique orderings of the letters in the word Mississippi are there? This question isn't exactly in the right form for what we've prepared for, but I think you can figure out the right answer. I'll give you a hint: Notice there are 11 letters but there aren't 11 distinct letters. Think about how to account for the non-unique letters (divide out the non-uniqueness).
Good Luck! Email me if you'd like to check your answers (email: michael@expertmathtutor.net).
|
|
|