x2
Introduction
( )
Types of Arrangements
=
Two More Methods
=
Some Applications

# 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
A permutation is an ordered arrangement of the objects in a set. A permutation with r elements is called an r-permutation.

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 SetNo. of Permutations
(Multiplication Rule)
Factorial Version
111!
21 · 2 = 22!
31 · 2 · 3 = 63!
41 · 2 · 3 · 4 = 244!
51 · 2 · 3 · 4 · 5 = 1205!
. . .
nn(n - 1)(n - 2) ... 2 · 1n!

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
If we have a set with n elements it has n! permutations.

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)

$$\frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot (3 \cdot 2 \cdot 1)}{3 \cdot 2 \cdot 1}$$

But if I rewrite that using factorials, it becomes

$$\frac{10!}{3}$$

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

$$\frac{10!}{(10 - 7)!}$$

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.

$$\frac{n!}{(n-r)!}$$
Permutation Formula 2
If we have a set with n elements, the number of permutations of r elements of the set is $$\frac{n!}{(n-r)!}$$ We will write the number of permutations of n elements into groups of r as nPr.