Skip to main content

Section 2.2 Permutations and Combinations

In this section we get a little bit fancier and define some special quantities that show up frequently when counting objects or rearrangements. First, recall that the factorial of \(n\) is shorthand for the product

\begin{equation*} n! = n \times (n-1) \times \cdots \times 1\text{,} \end{equation*}

which, as we saw in the previous section, can be used to count the number of ways to sit \(n\) people in a row for a concert.

Video: Permutations

Definition 2.2.1. Permutation.

A permutation is a bijection from a finite set \(S\) to itself.

Remark 2.2.2.

If \(|S| = n\text{,}\) then there are \(n!\) bijections \(S \rightarrow S\text{.}\) Equivalently,

  • There are \(n!\) ways to arrange \(n\) distinct objects in a row.
  • There are \(n!\) rearrangements of a word with \(n\) distinct letters. Each rearrangement is said to be a permutation of the \(n\) letters.

Let \(S = \{a,b,c,d\}\text{.}\) Then the function \(f: S \rightarrow S\) defined by

\begin{equation*} f(a) = b, f(b) = d, f(c) = c, f(d) = a \end{equation*}

is one example of a bijection from \(S\) to \(S\text{.}\) Since \(|S| = 4\text{,}\) there are a total of \(4! = 24\) bijections from \(S\) to itself.

What if we wanted to rearrange \(k\) of the \(n\) distinct objects (i.e. only a subset)?

How many three-letter words can be formed using the letters of the word

EQUATION?

Hint

How many choices do you have for the first letter? the second? the third? Use the Product Rule.

Answer

\(8 \cdot 7 \cdot 6 = 336.\)

Let's generalize this. Let \(k \leq n\text{,}\) and use the Product Rule to count the number of ways to arrange \(k\) objects in a row, taking from a set of \(n\) distinct objects.

Then express your answer in terms of factorials, and complete the statement of Proposition 2.2.5 below.

Remark 2.2.6.

When solving problems you may use either notation above and leave your answer in that form.

How many ways can a class of 45 students elect a president, vice-president, and secretary to represent them on student council?

Solution

This corresponds to the number of permutations of 45 objects taken 3 at a time, so the total is

\begin{equation*} 45 \cdot 44 \cdot 43 = 85140\text{.} \end{equation*}

One can also imagine the solution using the Product Rule: there are three steps to this operation:

elect a president: 45 choices
elect a vice-president: 44 choices
elect a secretary: 43 choices

Then the number of ways to do so is \(45 \cdot 44 \cdot 43\text{.}\)

  1. Count the number of three-letter words that can be formed from the letters of the word ZAHLEN.
  2. How many of the words from (a) contain only consonants?
  3. How many of the words from (a) contain contain exactly one vowel?
Hint

For part c., try using the Product Rule. What steps need to be performed to form a word that satisfies the given condition?

Answer

a. 120

b. 24

c. 72

The next example shows that having distinct objects is crucial in the statement of Definition 2.2.1.

Video: Permutations of a Multiset

Count the number of arrangements of the letters in the word YEET.

Solution A misguided attempt to apply Definition 2.2.1 will yield \(4! = 24\) possible arrangements of the word YEET. However, we see that there are only 12 possibilities when we list them all:

YEET YETE YTEE TYEE TEYE TEEY
EETY EEYT ETYE ETEY EYET EYTE

This is because the letters in the word YEET are not distinct! If we distinguish each letter E in the word by calling them E\(_1\) and E\(_2\text{,}\) then we see that each arrangement above actually came from two arrangements, for instance:

YE\(_1\)E\(_2\)T and YE\(_2\)E\(_1\)T \(\rightarrow\) YEET
YE\(_1\)TE\(_2\) and YE\(_2\)TE\(_1\) \(\rightarrow\) YETE

Thus while Definition 2.2.1 predicts \(4! = 24\) arrangements of the four letters Y, E\(_1\text{,}\) E\(_2\text{,}\) and T, we see that for each arrangement either E\(_1\) is somewhere to the left, or somewhere to the right of E\(_2\text{.}\) Hence we divide by two to account for this overcounting, which gives the correct number, \(4!/2 = 12\text{.}\)

What if three letter E's are repeated? Following the same reasoning, we can distinguish them first as E\(_1\text{,}\) E\(_2\text{,}\) and E\(_3\text{,}\) then apply Definition 2.2.1. We will get a number that overcounts the actual answer by a factor of 6 this time, since there are \(3! = 6\) ways to arrange the three E's:

E\(_1\)E\(_2\)E\(_3\) E\(_1\)E\(_3\)E\(_2\) E\(_2\)E\(_1\)E\(_3\)
E\(_2\)E\(_3\)E\(_1\) E\(_3\)E\(_1\)E\(_2\) E\(_3\)E\(_2\)E\(_1\)

We generalize this to Proposition 2.2.10, which gives a way to count rearrangements of words when some letters are repeated. (We say the letters are elements of a multiset, which generalizes sets to allow for multiple instances of elements.)

How many arrangements can be formed using the letters of the word

MISSISSAUGA?

Answer

\(\dfrac{11!}{1!\ 2!\ 4!\ 2!\ 1!\ 1!} = \dfrac{11!}{2!\ 4!\ 2!} = 415800.\)

Count the number of ways the letters of the word MATHEMATICS can be arranged so that

  1. The two M's are beside each other.
  2. The two M's are not beside each other.
  3. The word MATH appears somewhere in the arrangement.
Hint 1

a. Treat ‘MM’ as a single object.

Hint 2

b. How are parts a. and b. related?

Hint 3

c. Treat ‘MATH’ as a single object.

UTM Athletics is sending a team of 7 players to represent the university at an Ontario e-sports tournament called The Provincial. Suppose that a total of 30 students tried out for the team.

  1. How many possible teams can be formed from the students who tried out?

  2. Suppose further that there are different positions on the team, as follows

    • 1 carry player
    • 1 mid player
    • 1 offlane player
    • 2 support players
    • 2 reserve players

    How many possible teams can be formed from the students who tried out? Assume everyone who tried out can play every position. (Not usually the case in reality…)

Hint 1

a. Each student either makes the team, or doesn't. Express each possible team as a sequence of 30 labels, one for each student who tried out.

Hint 2

b. Same with a., but with more labels to account for the different positions on the team.

The scenario in part (a) of Checkpoint 2.2.13 is an example where the order in which the students are picked does not matter -- the team is just a collection (set) of 7 players. Here's a smaller example:

Adele is getting married soon, and due to space constraints at the venue, needs to pick exactly two of her five best friends (Mel B., Mel C., Emma, Geri, and Victoria) to be her bridesmaids. How many possible combinations are there?

Solution Each combination of bridesmaids corresponds to a rearrangement of three X's and two O's, given a fixed arrangement of the five names in a row; for instance, the arrangement

Mel B. Mel C. Emma Gerri Victoria
O X X O X

means that Mel B. and Gerri will be bridesmaids, while

Mel B. Mel C. Emma Gerri Victoria
X X X O O

corresponds to Geri and Victoria being chosen. Applying Proposition 2.2.10 to the three X's and two O's, we see that there are exactly \(\dfrac{5!}{2! 3!} = 10\) possible combinations.

Note When the usual formula for \(k\)-permutations from an \(n\)-set (Proposition 2.2.5)) is applied to the previous example, we get a total of \(\dfrac{5!}{(5-3)!} = 60\text{,}\) which is incorrect. The reason is that this formula treats the pairs

(Geri, Victoria)

and

(Victoria, Geri)

as different outcomes, while for this example they both correspond to the same combination of \(\{\text{Geri}, \text{Victoria}\}\) being chosen as bridesmaids, since the order doesn't matter.

Overcounting as a Counting Technique.

In the previous examples you may have been reminded of the main difference between an \(n\)-tuple \((a_1,a_2,\ldots,a_n)\) and a set of \(n\) elements \(\{a_1,a_2,\ldots,a_n\}\text{:}\) order.

To give a small example, the triples \((1,2,3)\) and \((3,1,2)\) are not equal in \(\mathbb{R}^3\text{,}\) and there are a total of six different triples using these same numbers:

\begin{align*} (1,2,3) \amp \amp (2,1,3) \amp \amp (3,1,2)\\ (1,3,2) \amp \amp (2,3,1) \amp \amp (3,2,1) \end{align*}

On the other hand, the sets \(\{1,2,3\}\) and \(\{3,2,1\}\) are equal—it doesn't matter how we write the three numbers since a set is defined by object membership.

In general, to count objects for which order does not matter, we can assume order matters first, then divide by the overcounting factor, typically the factorial of how many elements are under consideration.

As another example, in Proposition 2.2.10, each \(n_i!\) term in the denominator is the overcounting factor associated with first treating all objects of type \(i\) (there are \(n_i\) of them) differently.

When selecting \(k\) elements from a set of \(n\text{,}\) and if the order in which they are selected does not matter, we simply need to divide by \(k!\text{.}\)

Video: Combinations

Definition 2.2.15. Combination.

A combination of \(k\) elements taken from a set \(S\) of size \(n\) is any \(k\)-element subset of \(S\text{.}\)

A standard deck of cards consists of 52 cards, which come in 13 ranks (A/ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, J/jack, Q/queen, K/king) of four cards each, one for each suit: clubs \(\clubsuit\) (a black suit), spades \(\spadesuit\) (black), hearts \(\heartsuit\) (red), diamonds \(\diamondsuit\) (red).

  1. How many outcomes (or hands) are possible when you draw five cards at random from the deck?
  2. How many of these five-card hands comprise only numbered cards?
  3. How many of these five-card hands have exactly two red and three black cards?

Solution a. There are 52 distinct cards in the deck, and we are drawing five of them at random. Each outcome only depends on which cards are drawn, so the order in which we draw them does not matter. Therefore there are

\begin{equation*} \binom{52}{5} = \frac{52!}{47! \ 5!} = 2598960 \end{equation*}

possible five-card hands.

b. The ranks 2 to 10 are the numbered cards; there are a total of 36 numbered cards in a deck (9 ranks times 4 suits each). The number of five-card hands drawn from these cards is

\begin{equation*} \binom{36}{5}\text{.} \end{equation*}

c. The process of forming such a five-card hand can be broken down into two steps:

Step 1: Pick two red cards

Step 2: Pick three black cards

These two steps are independent of one another. There are 26 black and 26 red cards, so the Product Rule tells us that there are

\begin{equation*} \binom{26}{2}\binom{26}{3} \end{equation*}

five-card hands with this property.

Let \(0 \leq k \leq n\text{.}\) Using algebra it's straightforward to show that

\begin{equation*} \binom{n}{k} = \binom{n}{n-k}\text{.} \end{equation*}

Without using algebra, explain why \(\displaystyle\binom{n}{k}\) is equal to \(\displaystyle\binom{n}{n-k}\) by counting the number of \(k\)-subsets of \(\{1,2,\ldots,n\}\) in two ways.

Hint

The first way is the usual way. For the second way: select elements that will not be put in the \(k\)-set.

Exploration 2.2.1. Early Combinatorics.

Some of the earliest mentions of permutations and combinations occur in ancient Hindu texts dating back to the year 600 BC. Called vikalpa and bhaṅga, respectively, they were used in the study of Vedic meters in poetry, in architecture, in medicine, astrology, and other areas.

The following examples are taken from [6].

(a)

The Suśruta-saṃhitā, (est. 500 BC) an ancient Hindu text on medicine and surgery, counts the number of combinations of the flavours sweet, acid, saline, pungent, bitter, and astringent taken two at a time, in the following way:

“On making two combinations in successive way, those beginning with sweet are found to be 5 in number; those beginning with acid are 4; those with saline 3; those with pungent 2; bitter and astringent make 1 combination.”

―Suśruta-saṃhitā lxiii, as cited in [6], p. 358

Explain how this computes \(\displaystyle\binom{6}{2}\text{.}\)

(b)

This excerpt from the Anuyogadvāra-sūtra (c. 500) explains how to compute \(6!\text{.}\)

“What is the direct arrangement? Dharmāstikāya, Adharmāstikāya, Ākāśāstikāya, Jīvāstikāya, Pudgalāstikāya and Addhāsamaya—this is the direct arrangement. What is the reverse arrangement? Addhāsamaya, Pudgalāstikāya, Jīvāstikāya, Ākāśāstikāya, Adharmāstikāya, and Dharmāstikāya—this is the reverse arrangement. What are the mixed arrangements? From the series of numbers beginning with one and increasing by one up to six terms. The mutual products of these minus 2 will give the number of mixed arrangements.”

―Anuyogadvāra-sūtra, Sūtra 97, as cited in [6], p. 363.

Discuss what mixed arrangement refers to and how the computation of \(6!\) is carried out.

Solutions Solutions to Selected Checkpoints

Checkpoint 2.2.12. MATHEMATICS.
Solution
Checkpoint 2.2.18. Esports Tournament, again.
Solution