Permutations

Section 3.2 Permutations

Consider a collection of objects. To permute these objects means to rearrange their order. A permutation is one of these such rearrangements, or orderings. Intuitively, it is a way to “sequence” or “line up” the objects. The fundamental counting principle allows us to determine the number of ways to arrange objects, or the number of permutations of objects.

Example 3.2.1.

How many different ways are there to arrange 5 people in a line? By the fundamental counting principle, there are 5 selections in total. For the first spot, we can choose any of the 5 people. For the second spot, we can choose anyone except the 1st person, so there are 4 options. For the 3rd spot, there are 3 options as we can't choose the 1st nor 2nd person. For the 4th spot, there are only 2 options. Finally, for the last spot, there is only 1 person left, so there is only 1 option. Thus, in total, the number of ways to arrange 5 people is given by,

\begin{equation*} 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5! = 120 \end{equation*}

Subsection 3.2.1 Permutations of Objects

More generally, consider the permutations of $n$ objects. This can be viewed as a series of choices, filling in $n$ positions using the $n$ objects. For the first spot, we can choose any of the $n$ objects, and so there are $n$ choices. For the second spot, one of the objects has been taken, so there are $n-1$ choices for the object in the 2nd position. Similarly, there $n-2$ for the 3rd position, and so on. For the second-last object, there will be 2 positions left and so there are 2 choices, and the last object will only have one available slot left, and so there will be only 1 choice. In summary,

Theorem 3.2.2. Permutations of $n$ objects.

The number of permutations of $n$ objects is $n!\text{.}$

Example 3.2.3.

Consider $n$ boys and $n$ girls. Consider the number of ways that they can form couples (assume only couples of mixed gender). The first boy can “choose” from all $n$ of the girls (you could view this as the girls choosing boys, it would be equivalent). Then, the second boy has $n-1$ choices, the third has $n-2$ choices, and so on. Thus, there are $n(n - 1)(n - 2) \cdots 2 \cdot 1 = n!$ ways to form these couples.

Subsection 3.2.2 Permutations of $r$ Elements from $n$ Elements

Definition 3.2.4.

A permutation of $r$ elements from a set of $n$ unique elements is any of the specific orderings or arrangement, without repetition, of $r$ elements.

Each rearrangement of these $r$ elements is a different permutation. Of course, here $r$ is an integer and $1 \leq r \leq n\text{.}$

Consider these $n$ elements taken $r$ at a time. Using the FCP, there are $n$ ways to choose the first of the $r$ elements, $n-1$ ways to choose the second element, and so on. For each element, there are $n - (\text{object number} - 1)$ ways to choose it. Thus, there are $n - (r - 1) = n - r + 1$ ways to choose the $r$th (the final) element. Thus,

\begin{align*} \nPr{n}{r} \amp = n(n - 1)(n - 2) \cdots (n - r + 1)\\ \amp = n(n - 1)(n - 2) \cdots (n - r + 1) \cdot \frac{(n - r)!}{(n - r)!} \amp\amp \text{multiplying and dividing by $(n - r)!$}\\ \amp = \frac{n(n - 1)(n - 2) \cdots (n - r + 1)(n - r)!}{(n - r)!}\\ \amp = \frac{n!}{(n - r)!} \end{align*}

In summary,

Theorem 3.2.5.

The number of permutations of $n$ unique objects taken $r$ at a time is denoted by $\nPr{n}{r}\text{,}$ and is given by,

\begin{equation*} \boxed{\nPr{n}{r} = \frac{n!}{(n - r)!}} \end{equation*}

This formula is a generalization of the FCP. If there are $n$ elements taken $n$ at a time, then using the permutation formula,

\begin{equation*} \nPr{n}{n} = \frac{n!}{(n - n)!} = \frac{n!}{0!} = \frac{n!}{1} = n! \end{equation*}

which is consistent with the FCP. Also, notice that these two methods mean that the following equality must hold,

\begin{equation*} \underbrace{\frac{n!}{0!}}_{\text{from permutation formula}} = \underbrace{n!}_{\text{from FCP}} \end{equation*}

Thus, $0!$ must be equal to 1. This is one reason why zero factorial is defined to be one.

Recall that a permutation of $r$ elements from an $n$ element set consists of choosing $r$ elements from the set in a particular order. We can view this as choosing an “ordered subset” of $r$ elements from an $n$ element set.

Example 3.2.6.

Consider $\nPr{n}{1}\text{,}$ the number of permutations of $n$ objects taking 1 at a time. Intuitively, we know that there are $n$ permutations (one for choosing each of the $n$ objects). Using the permutation formula,

\begin{equation*} \nPr{n}{1} = \frac{n!}{(n - 1)!} = \frac{n(n - 1)!}{(n - 1)!} = n \end{equation*}

Example 3.2.7.

How many different signals can be made by using at least 4 different flags from a selection of 6 different flags?

Signals are different depending on the order of the flags presented. At least 4 different flags means a signal could use 4, 5, or 6 flags. Thus, the number of different signals is given by,

\begin{equation*} \nPr{6}{4} + \nPr{6}{5} + \nPr{6}{6} = 720 + 720 + 360 = 1800 \end{equation*}

Example 3.2.8.

A race has 7 competitors. Determine the number of ways the 1st, 2nd, and 3rd place medals be awarded.

When choosing these 3 medals, order matters. So, there are $\nPr{7}{3} = 210$ ways.

Discrete Math