Section 1.5 – Permutations and Combinations (Part 1)
Permutations
We actually spent most of Section 1.2 talking about these but we've made it to the point where we need a formal definition.
Permutations
Suppose we started with a set of people: {Alice, Ben, Christy, David}. Some permutations of the set would be
| {David, Christy, Ben, Alice} | {David, Ben, Alice, Christy} |
| {Christy, Ben, David, Alice} | {Alice, Ben, David, Christy} |
In Section 1.2, we used the Multiplication Rule to count the total number of permutations of the set, i.e. the total number of ways the four names can be arranged or listed. Each arrangement/list is a different permutation. In this case, all of the permutations are 4-permutations because they each have 4 names in them. {David, Christy, Alice} would be a 3 permutation and {David, Christy} would be a 2-permutation.
Using our new terms, we could rephrase the question, "How many ways can four people be put in a line with three people?" as, "How many 3-permutations are there of a set with four items?"
If we combine the factorials that you learned about in Section 1.3 and the multiplication rule from Section 1.2, we can come up with a formula for the number of permutations of a set. To see the pattern, look at these examples:
| Size of the Set | No. of Permutations (Multiplication Rule) | Factorial Version |
|---|---|---|
| 1 | 1 | 1! |
| 2 | 1 · 2 = 2 | 2! |
| 3 | 1 · 2 · 3 = 6 | 3! |
| 4 | 1 · 2 · 3 · 4 = 24 | 4! |
| 5 | 1 · 2 · 3 · 4 · 5 = 120 | 5! |
| . . . | ||
| n | n(n - 1)(n - 2) ... 2 · 1 | n! |
The pattern you should see in the table is that the number of permutations is equal to the factorial of the number of elements in the set. For example, the number of permutations of a set with 10 elements is 10!.
Permutation Formula 1
This formula assumes that we are looking at permutations of the entire set. For example, the number of ways that 10 people can be seated in a row of 10 chairs. Now, suppose that we only have seven chairs. The Multiplication Rule tells us that we have
10 · 9 · 8 · 7 · 6 · 5 · 4 = 604, 800
When I look at 10 · 9 · 8 · 7 · 6 · 5 · 4, I see the beginning of 10! but with the last 3 factors, 3 · 2 · 1 missing. So if I start with 10 · 9 · 8 · 7 · 6 · 5 · 4, I can make that into a fraction by multiplying it by (3 · 2 · 1) / (3 · 2 · 1)
But if I rewrite that using factorials, it becomes
Now think about the 3 for a minute. We started with 10 elements (people) and put them in groups of 7 (chairs). Notice how 3 = 10 - 7. It may seem a little awkward but if we write the 3! as (10 - 7)! our expression becomes
What makes that helpful is that all of the numbers in the expression are numbers in the original question. If we replace the number of people (10) with n and the number of chairs (7) with r our formula becomes/p>
In a permutation, the order of the items in the list matters. In the next section, we'll look at the situation where the order doesn't matter.