Permutations

Imagine that you have three fruits: an apple, an orange, and a banana. You want to eat all three fruits, one after the other. In how many ways can you order the fruits?

A permutation of a set of objects is a specific linear arrangement of such objects. For example, $\text{[banana, orange, apple]}$ is a permutation of the three fruits. Enumerating permutations is useful for counting problems where the order is important, such as for the problem above. Combinatorics is a field of mathematics that deals with the number of arrangements, subject to certain conditions, that can be made up of elements of a given set. Keep reading to see how to solve the problem above.

Permutations of distinct objects

Let's revisit the problem from the introduction. If you eat the apple first, then you have to choose an order for the remaining fruits. The next fruits can be: orange, then banana; or banana, then orange. Likewise, if the first fruit is orange, the next fruit can be: apple, then banana; or banana, then apple. Similarly, if the first fruit is banana, then either apple, then orange, or orange, then apple come next. So there are six different ways to order the fruits.

In general, you can think of finding a permutation of a set with $n$ distinct elements as an $n$-step operation:

1. Choose the first element from the set of $n$ elements.
2. Choose the second element from the remaining $n-1$ elements.

…
n. Choose the remaining element.

The number of permutations of a set is equal to the number of ways you can perform the operation. You can calculate this by the rule of product. There are $n$ ways to perform the first step, $n-1$ ways to perform the second step, and so on until the final step where there is one element left.

The number of permutations of a set of $n$ distinct elements, which is denoted by $P_n$, is determined by the formula:

$P_n = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 3 \cdot 2 \cdot 1 = n!$

$n!$ is a designation that is used to mean the product of all natural numbers from 1 to $n$ inclusive, and is called "$n$-factorial". We define $0! = 1$.

Thus, the total number of permutations of three fruits is $P_3 = 3 \cdot 2 \cdot 1 = 6$, which is exactly what we counted above.

Two-line notation

In general, there can be so many permutations that two of them look a lot alike. It would be nice to have a more compact notation to visualize them. The two-line notation is one such notation.

The two-line notation for permutations allows us to specify a particular arrangement of elements, with emphasis on the position of the elements. In this notation, numbers are used to represent elements. The first row is the numbers in natural order $(1, 2, 3,...)$. The second line contains the ordering of the elements.

For example, the permutation $[3, 4, 2, 1]$ in two-line notation would be written as

$\begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 4 & 2 & 1 \end{pmatrix}$

Permutations with repeated objects

Let's look at two problems that seem similar but need different approaches for solving them.

The first problem is the following. How many ways can the letters in the word $\text{COMPUTER}$ be arranged in a row? Since each of the eight letters in the word is distinct, the number of permutations is $8! = 40320$.

The second problem is the following. How many ways can the letters in the word $\text{STATISTICS}$ be arranged in a row? In this case, some letters in the word are repeated. There are three $\text{S}$'s, three $\text{T}$'s, one $\text{A}$'s, two $\text{I}$'s, and one $\text{C}$.

If the letters were different, then there would be $10!$ permutations. However, for a particular permutation, since there are three $\text{S}$'s, the repeated $\text{S}$'s can be arranged in $3!$ ways to give the same arrangement of the word. Likewise, there are two $\text{I}$'s, so the repeated $\text{I}$'s can be arranged in $2!$ ways to give the same arrangement of the word. We can take repetition into account by dividing by the total number of repeated arrangements. We get the following result:

$\frac {10!}{3! \cdot3! \cdot 1! \cdot 2! \cdot 1!} = 50400$

In general, if there are $n$ total objects with $n_1$ identical objects of one type, $n_2$ objects of a second type, and so on until the last type with $n_k$ objects, the number of permutations of these $n$ objects are

$\frac {n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!}$

Another example

Let's consider the following example:

$\text{A bookshelf holds 40 different books. How many ways can they be} \\ \text{ arranged such that books 1 and 2 do not stand side by side?}$

The strategy to solving this problem is to count the number of permutations where the books are together, and then use the difference rule to calculate the number of permutations where the books are not together.

We determine the total number of permutations of $40$ elements by the formula: $P_{40} = 40!$.

To calculate the number of "extra" permutations, we first determine how many variants there are where the 2nd book is on the right of the 1st. In such permutations, the 1st book can take places from the first to the 39th, and the 2nd from the second to the 40th– only $39$ places for this pair of books. And for each such position of the first two books, the remaining $38$ books can occupy the remaining $38$ places in no particular order. Permutation options for $38$ books: $P_{38} = 38!$. In total, if the 2nd book is located to the right of the 1st book, there will be $39 \cdot 38!=39!$.

Similarly, let's consider the case when the 2nd book is located next to the 1st, but to the left of it. With the same reasoning as before, the number of options is $39 \cdot 38!=39!$.

This means that there are $2 \cdot 39!$ "superfluous" permutations. And the necessary arrangement methods are $40!-2 \cdot 39!$. Let's calculate this value:

$40! = 39! \cdot 40; \ \ 40! - 2 \cdot 39! = 39! \cdot (40-2) = 39! \cdot 38$

Therefore, there are $39! \cdot 38$ ways to arrange forty books such that the first and second are not next to each other.

Conclusion

Permutations are specific orderings of the elements of a set. The two-line notation is useful for visualizing a permutation compactly. As an example, a specific ordering of the elements $\{ 1, 2, 3 \}$ in two-line notation is

$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}$

The total number of permutations of $n$ different elements is equal to $n!$. When there are repeated elements, this number is divided by the number of repeated arrangements.