Skip to main content

Discrete Mathematics for Computing (Draft)

Christine Caples, Adam Gilbert, Melanie Fraser

Section 4.3 Arrangements and Permutations

In this section we encounter methods for counting the number of arrangements (or orderings) of items selected from a collection of options. Unlike the previous section, we do not allow items to be selected more than once here. You might think of choosing the way in which people line up for a photograph as your paradigm here. In fact, that’s the context with which we’ll motivate our discussion below.

Subsection 4.3.1 Motivation

Consider the context of families lining up for a wedding photo. The bride’s family has 5 people (including her) and the goom’s family has 4 people (including him). Perhaps we want to know the total number of ways these individuals could line up (left to right) for a photograph.
There are lots of restrictions we could impose on the ordering. Let’s see several examples below.

Example 4.3.1. A Wedding Photo, Part I.

The families described above would like to line up to take a photograph together. In the spirit of the marriage and becoming one large family, there are no restrictions on the lineup and who is standing next to one another. In how many ways can the individuals in this photo be arranged from left to right?
Answer.
Notice that there will be 9 total people in the photograph -- the five total members of the bride’s family and the four total members of the groom’s family. We can think of the photo lineup using the "picture" below.
\begin{gather*} ~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~ \end{gather*}
Because nobody has been positioned yet, there are 9 individuals who could be placed into the left-most position.
\begin{gather*} ~9~~\cdot~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~ \end{gather*}
Once that first person has been placed, there are only eight individuals left to position. That is, for any choice of the person to place into the leftmost position, there are eight choices of person to place next to them. The Fundamental Principle of Counting then suggests that there are \(9\cdot 8\) ways to arrange people into the two leftmost positions.
\begin{gather*} ~9~~\cdot~~8~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~ \end{gather*}
Continuing in this fashion, there are seven individuals to place in the next position, followed by six for the one after, continuing on until we are left with only the last person to place into that final position.
\begin{gather*} ~9~~\cdot~~8\cdot~~7~~\cdot~~6~~\cdot~~5~~\cdot~~4~~\cdot~~3~~\cdot~~2~~\cdot~~1 \end{gather*}
Multiplying, we obtain \(\boxed{~362,880~}\) total arrangements for that one photo!

Definition 4.3.2. Factorial.

The product \(9\cdot 8\cdot 7\cdot\cdots\cdot 2\cdot 1\) used above is a type of product that appears so often in mathematics that it is given a special name and notation. That product can be read as 9 factorial and is often denoted as \(9!\text{.}\) In general, n factorial is written as
\begin{gather*} n! = n\cdot\left(n-1\right)\cdot\left(n-2\right)\cdot\cdots\cdot \left(2\right)\cdot\left(1\right) \end{gather*}
Let’s explore some more restrictive versions of our wedding photo arrangement.

Example 4.3.3. A Wedding Photo, Part II.

Assume that we want a photo where the bride and groom are positioned in the center of the photo, with the groom to the left of the bride, the groom’s family to the left of the groom, and the bride’s family to the right of the bride. How many different arrangements of the individuals for the photo satisfy these requirements?
Answer.
This photograph is more restrictive than the previous one. Because of this we should expect that there are fewer arrangements resulting in an acceptable photo. Since the groom’s family should be to the left of the groom and the bride’s family to the right of the bride, we know that the groom must occupy the position fourth from the left and the bride must occupy the position fifth from the left. Let’s start with such an arrangement. We’ll let G stand for the groom and B stand for the bride.
\begin{gather*} \underline{~~~}~~\underline{~~~}~~\underline{~~~}~~G~~B~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~} \end{gather*}
Notice that there is no choice in the placement we just made. There is exactly one way to have the groom occupy the fourth position from the left and the bride occupy the fifth position. We do have some choice in how to fill in the remaining positions though.
\begin{gather*} \underbrace{\underline{~~~}~~\underline{~~~}~~\underline{~~~}}_{\text{Groom's Family}}~~G~~B~~\underbrace{\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}}_{\text{Bride's family}} \end{gather*}
Now, since there are three remaining members of the groom’s family, we have three options for who will occupy the leftmost position, two who will occupy the next position and then the final member of the groom’s family will fill in the position just to the left of the groom.
\begin{gather*} \underbrace{\underline{~3~}~\cdot~\underline{~2~}~\cdot~\underline{~1~}}_{\text{Groom's Family}}~~G~~B~~\underbrace{\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}}_{\text{Bride's family}} \end{gather*}
Similarly, we can fill in the positions to the right of the bride. We need only remember that there are four additional members of her family.
\begin{gather*} \underbrace{\underline{~3~}~\cdot~\underline{~2~}~\cdot~\underline{~1~}}_{\text{Groom's Family}}~~G~~B~~\underbrace{\underline{~4~}~\cdot~\underline{~3~}~\cdot~\underline{~2~}~\cdot~\underline{~1~}}_{\text{Bride's family}} \end{gather*}
Recalling that there was no choice in how the bride and groom were positioned, we use the Fundamental Principle of Counting to compute the total number of arrangements for the photo.
\begin{gather*} \left(3\cdot 2\cdot 1\right)\cdot\left(4\cdot 3\cdot 2\cdot 1\right) = \boxed{~144~} \end{gather*}
Adding those additional restrictions drastically reduced the number of acceptable arrangements for the photo. We went from \(362,880\) arrangements for the unrestriced photo to only \(144\) arrangements for the photo with these restrictions!
What if not everyone needs to be in the photo? Perhaps the photographer wants a random subset of six individuals for the photo. Consider the example below, which introduces the notion of permutations. After this, you’ll have an opportunity to practice what you’ve learned!

Example 4.3.4. A Wedding Photo, Part III.

The wedding photographer has set up a photo booth which can accommodate six people at a time. In how many ways can six members of the wedding party arrange themselves (left to right) for a photo in the photo booth?
Answer.
While there aren’t positional restrictions on this photo, there is a size restriction. Not all of the nine family members will be able to be in the picture. That being said, the approach is still the same. We have six positions to fill.
\begin{gather*} \underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~} \end{gather*}
We’ll fill each of the positions above. All nine of the family members are available to fill the leftmost position.
\begin{gather*} \underline{~9~}~\cdot~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~} \end{gather*}
Once the family member has been chosen to take the leftmost position, there are eight faily members available for the next, and so on until all of the positions have been filled.
\begin{gather*} \underline{~9~}~\cdot~\underline{~8~}~\cdot~\underline{~7~}~\cdot~\underline{~6~}~\cdot~\underline{~5~}~\cdot~\underline{~4~} \end{gather*}
Notice that all of the positions for the photo have been filled. The remaining three family members will not be in the photo, so their positional order does not matter. The total number of arrangements for a family photo in the photo booth are
\begin{gather*} 9\cdot\left(8\right)\cdot\left(7\right)\cdot\left(6\right)\cdot\left(5\right)\cdot\left(4\right) = \boxed{~60,480~}~ \end{gather*}
That is, there are 60,480 different arrangements for the photo booth photo which will include six of the nine family members.
As with factorials, the type of product we used above (a factorial with its tail end cut off) appears commonly in mathematics and is referred to as a permutation. A definition appears below.

Definition 4.3.5. Permutation.

A permutation of \(k\) elements from a collection of size \(n\text{,}\) where \(k\leq n\text{,}\) counts the number of ways to arrange (order) those \(k\) elements. The notation and definition for a permutation of \(k\) elements from a collection of \(n\) appears below:
\begin{gather*} _n P_k = \frac{n!}{\left(n - k\right)!} = n\cdot\left(n - 1\right)\cdot\cdots\cdot\left(n - \left(k-1\right)\right) \end{gather*}

Subsection 4.3.2 Interactive Examples Involving Permutations

Now that you’ve seen a few examples and have been exposed to the notion of factorials and permutations, use what you’ve learned to solve the embedded exercises below.

Checkpoint 4.3.6. Creating "Words" from an Alphabet.

Checkpoint 4.3.7. Choosing Club Leadership.

Checkpoint 4.3.8. Choosing a Restrictive Password.

Checkpoint 4.3.9. Building a Relay Team.

In this section you discovered and applied the factorial as a mathematical operation which counts the number of ways we can arrange \(n\) elements into an ordering. Additionally, you saw and applied permutations as a way to arrange a subset of a collection of objects into an ordering where not all of the objects in the collection are utilized. In the next section, we’ll discover how to count the number of ways to select a subset of items from a collection when the order of selection does not matter.
PrevTopNext