Skip to main content
\(\renewcommand{\chaptermark}[1]{\markboth{\MakeUppercase{ #1}}{\thechapter~ #1}} \renewcommand{\sectionmark}[1]{} \newcommand{\abs}[1]{\left|#1\right|} \renewcommand{\theenumi}{5.\arabic{enumi}} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\norma}[1]{\left\|#1\right\|} \newcommand{\BM}[1]{\text{\boldmath$#1$}} \newcommand{\halmaz}[1]{\left\{\,#1\,\right\}} \newcommand{\halmazvonal}[2]{\left\{\,#1\mid #2\,\right\}} \newcommand{\halmazpont}[2]{\left\{\,#1:#2\,\right\}} \newcommand{\N}{\mathbb{N}} \newcommand{\len}{\norm} \newcommand{\var}[2][]{v_{#1}\left(#2\right)} \newcommand{\vari}[2]{v_{#1}\left(#2\right)} \newcommand{\size}[2][]{s_{#1}\left(#2\right)} \newcommand{\dep}[2][]{d_{#1}\left(#2\right)} \newcommand{\sizestar}[2][]{s_{#1}^*\left(#2\right)} \newcommand{\depstar}[2][]{d_{#1}^*\left(#2\right)} \renewcommand{\headrulewidth}{0pt} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section2.3Permutations

Three students are taking an oral exam in Mathematics. After the usual half hour preparation time, one by one they tell the examiner about the theorem the examiner gave them. In how many different order can they do the exam? Let the three students be Alice, Beth and Claire.

It is not hard to list all possibilities. For example, Alice can start the exam, and then Beth follows and Claire finishes, or Claire follows and Beth finishes. Similarly, Beth can start with the exam, then Alice can follow and then Claire, or Claire and then Alice. Finally, Claire may start, and Alice continues and then Beth, or Beth continues and Alice finishes. Table 2.3.1 lists all six possibilities.

first second third
Alice Beth Claire
Alice Claire Beth
Beth Alice Claire
Beth Claire Alice
Claire Alice Beth
Claire Beth Alice
Table2.3.1The orders in which Alice, Beth and Claire can take the exam

Looking at Table 2.3.1, one can think of a general argument, as well. There are three ways to choose who the first person will be (Alice, Beth or Carrie). Then no matter what that choice was, there will be two possibilities left for choosing who the second person will be (the second person cannot be whoever was the first one). Then the person left will take the exam as the third. Altogether, this is \(3 \cdot 2 \cdot 1 = 6\) possibilities.

At the next exam, there are four students: Ed, Frank, George, Hugo. This time they decide in advance in what order they want to do the exam. In how many different orders can they do the exam?

List all possibilities for Ed, Frank, George and Hugo to find an order for themselves.

Let us try to use our new argument. There are four possibilities for choosing the person who starts the exam. Then, no matter who starts, there are three possibilities for choosing the second person (as the first person has already been chosen). Then there are only two possibilities for the third person, and whoever remains will be the fourth. That is, altogether they have \(4 \cdot 3 \cdot 2 \cdot 1 = 24\) possibilities to choose the order to do the exam.

What was the common in these two exercises (apart from the exam)? The fact that in both cases we needed to count the number of different orders of the people. In general, if there are \(n\) elements, then we call an ordering of these elements a permutation. Now, what happens if we need to count the number of permutations of \(n\) elements? It can be calculated similarly, e.g. the result would be \(n \cdot (n-1) \cdot \dots \cdot 2 \cdot 1\text{.}\) This is the number we denoted by \(n!\) in Section 1.2.

A permutation is an ordering of the \(n\) elements. We have \(n\)-many ways to choose the first element, then \((n-1)\)-many ways to choose the second element (we cannot choose the first anymore), then \((n-2)\)-many ways to choose the third element, etc. Thus the number of different ways we can put these \(n\) elements into an order is

\begin{equation*} n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 2 \cdot 1 = n!\text{.} \end{equation*}

Note, that permutations may arise in many situation. Recall that at the beginning of Chapter 2, Alice, Beth, Claire, Diane, Ed, Frank, George and Hugo wanted to form four dancing couples. Then Alice chose a partner first, then Beth, then Claire, and finally Diane. That is, their choosing put an order on the four boys, and therefore determined a permutation of them. And indeed, there are \(4!=24\) permutations of the four boys, and they can form four dancing couples in \(4!=24\)-many ways, as well.

How many four digit numbers exist, where all of the digits \(1\text{,}\) \(2\text{,}\) \(3\text{,}\) \(4\) appear exactly once?

How many four letter long (not necessarily meaningful words) can be built from the letters \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) \(d\text{,}\) if all letters must be used exactly once?

Five boys and three girls buy cinema tickets. They receive the tickets in the same row, their seats are numbered from 1 to 8. How many different ways can they sit on the seats? How many different ways can they sit on the seats if boys sit on seats from 1 to 5, and girls sit on seats from 6 to 8?