Permutations
In how many ways can 8 runners cross the finishing line? How many different passwords can you make with 7 digits without repeating any of them? These are questions of combinatorics: counting without having to write out the whole list. You are going to learn how to count arrangements, which is the first and most basic of the techniques.
Counting with the branching principle
Imagine you are going to seat 3 friends (Ana, Berta and Carla) on 3 chairs in a row. For the first chair you have 3 options. Once that one is chosen, only 2 people are left for the second chair. For the third chair, only 1 is left.
Each branch of the tree is a different way of seating them. The tree has $3 \cdot 2 \cdot 1 = 6$ paths from the root to a leaf: 6 possible arrangements.
Notice that once a person has been chosen for a chair, that person is no longer available for the following ones: the number of options goes down one at a time. This is exactly what distinguishes a permutation.
A local radio presenter must schedule exactly $5$ different songs during the next hour of broadcasting. In how many ways can they set the order in which the songs will…
A local radio presenter must schedule exactly $5$ different songs during the next hour of broadcasting. In how many ways can they set the order in which the songs will be played?
Permutations of n distinct objects
Following the same reasoning as in the tree, but with $n$ objects: for the first place there are $n$ options, for the second $n-1$, for the third $n-2$, and so on until only $1$ option is left for the last place.
$$P_n = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$$This product is called the factorial of $n$ and is written $n!$. So $P_n = n!$. You will study it in detail in the next section; here you only need to know that it is calculated by multiplying all the natural numbers from $n$ down to $1$.
In an athletics competition, $8$ runners participate in the final of the $100$ metres sprint. Assuming there are no ties, in how many different ways can they cross the…
In an athletics competition, $8$ runners participate in the final of the $100$ metres sprint. Assuming there are no ties, in how many different ways can they cross the finish line and be classified?
In a contemporary art gallery, $6$ paintings by the same artist are going to be displayed in a row along a wall. In how many different ways can the works be visually…
In a contemporary art gallery, $6$ paintings by the same artist are going to be displayed in a row along a wall. In how many different ways can the works be visually arranged?
Sometimes it is useful to fix one position before counting the others. If a password of 7 different digits (from 1 to 7) must always start with 7, that first digit no longer counts as a free choice: only the other 6 digits remain to be arranged in the remaining 6 positions, that is, $P_6 = 6! = 720$ passwords.
Four male friends and three female friends go to the cinema and buy tickets for seven consecutive seats in the same row. In how many ways can they sit if the four boys…
Four male friends and three female friends go to the cinema and buy tickets for seven consecutive seats in the same row. In how many ways can they sit if the four boys want to sit together and the three girls also want to sit together?
Permutations with repeated objects
How many different words can be formed by rearranging the letters of $SUN$? The three letters are different, so it is $P_3 = 3! = 6$: SUN, SNU, USN, UNS, NSU, NUS.
But what about the letters of $ANA$? Here there is one letter, $A$, that appears twice. If you treated the two "A"s as if they were distinguishable ($A_1$ and $A_2$), you would have $3! = 6$ arrangements, but half of them are indistinguishable from each other when read: $A_1NA_2$ and $A_2NA_1$ are, in fact, the same word ANA.
Calculate how many different words, whether or not they make sense in Spanish, can be formed by arranging all the letters of the word $BIOLOGIA$.
Calculate how many different words, whether or not they make sense in Spanish, can be formed by arranging all the letters of the word $BIOLOGIA$.
On the mast of a sailing boat, $7$ flags are to be hoisted to transmit a signal to the shore. There are $3$ red flags, $2$ blue flags and $2$ yellow flags available, all…
On the mast of a sailing boat, $7$ flags are to be hoisted to transmit a signal to the shore. There are $3$ red flags, $2$ blue flags and $2$ yellow flags available, all of the same size. How many different signals can be sent using all the flags?
Circular permutations
In a row, the first and the last places are different. At a round table there is no "first seat": all that matters is the order of people relative to one another. That is why rotating the whole group by one seat does not count as a new arrangement.
A group of $5$ friends goes to a pizzeria for dinner and decides to sit around a circular table. In how many different ways can they be seated?
A group of $5$ friends goes to a pizzeria for dinner and decides to sit around a circular table. In how many different ways can they be seated?
Back to the start: To form a password by rearranging 7 given digits without repeating any, you have $P_7 = 7! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5\,040$ different options.