Arrangements

In a previous topic, you got to know permutations, which are orderings of a list of elements. You learned how to calculate the number of different permutations of $n$ elements. This is useful, but there are cases when you want to count the permutations of only some $n$ elements instead of all of them. For example, suppose you want to count the number of possible $6$-letter passwords that contain only lowercase letters. Here, you do not want to count the permutations of all $26$ letters. Instead, you want to count the ways you can choose and permute $6$ letters. In this topic, you will learn how this counting can be done both when repetition of elements is and is not allowed in the permutation. In case you are curious, there are $165,765,600$ possible passwords if repetition is not allowed and $308,915,776$ if repetition is allowed. Keep reading to understand how these calculations are done.

Arrangements without repetition

Let's consider the problem of counting possible passwords. To simplify, let's consider an alphabet of four characters and passwords of length $2$. Given the set $\text{\{w, x, y, z\}}$, in how many ways can you choose two different letters and write them in order if a letter cannot be chosen more than once?

Let's list out the different pairs of letters as follows.

$\text{wx, xw, wy, yw, wz, zw, xy, yx, xz, zx, yz, zy}$

There are $12$ pairs. Each of these orderings of two elements is called a $2$-permutation of the set $\text{\{w, x, y, z\}}$.

A $k$-permutation of $n$ without repetition is a sequence of $k$ distinct elements of a set of $n$ elements. The number of $k$-permutations denoted $P(n, k)$ or $P_{n}^k$. It is calculated as follows.

$P(n, k) = P_{n}^k = {n! \over (n-k)!}$

In general, finding a $k$-permutation of a set with $n$ distinct elements can be thought of as a $k$-step operation:

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

…
k. Choose the $k$th element from the remaining $n-k+1$ elements.

The number of $k$-permutations of a set is equal to the number of ways the above operation can be performed. 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 are $n-k+1$ elements left. This gives the formula:

$P_{n}^k = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1)= {n! \over (n-k)!}$

In the problem at the start of this section, the given set contains no repeating elements. Using the formula for the number of $2$-permutations of $4$, you get the answer $12$, which is precisely what you enumerated above. $P_{4}^2 = {4! \over (4-2)!} = {24 \over 2} = 12$

Arrangements with repetition

Let's consider a problem that is similar to the one given in the previous section. Given the set $\text{\{w, x, y, z\}}$, in how many ways can you choose two letters and write them in order? The chosen letters can be the same.

$\text{ww, wx, xw, wy, yw, wz, zw, xx, xy, yx, xz, zx, yy, yz, zy, zz}$

You count $16$ ways. Note how the answer has changed from the example in the previous section.

A $k$-permutation of $n$ with repetition is a sequence of $k$ elements of a set of $n$ elements. The number of such $k$-permutations is calculated as $n^k$:

$R(n, k) = R_{n}^k = n^k$

Like with arrangements without repetition, choosing a $k$-permutation can be thought of as a $k$-step process. However, in this case repetition is allowed, so each step has the $n$ options. $k$ elements are selected from a set of $n$ elements, and the same elements can be selected multiple times. By the rule of product, $R_{n}^k = n^k$.

Revisiting the problem from the start of this section, we calculate $R_{4}^2 = 4^2 = 16$, which is exactly what we counted.

A complex example

Let's consider a slightly trickier example.

Suppose that there are $9$ seats in a row. There are $6$ adults and $3$ children. How many seating arrangements are possible where every child has an adult to his/her immediate left and right seats?

We can start off by arranging just the adults in a row: there are $6!$ ways to do this. There are $5$ spots between the adults where the $3$ seats for the children can be placed. Placing a child into one of these spots ensures that they have an adult to their immediate right and left. $3$ of the $5$ available spots need to be chosen to seat the children: the number of seating arrangements of the children is $P(5,3)$ (no repetition is allowed, because a child cannot sit in two seats at the same time). The total number of seating arrangements of everyone is calculated by the product rule: $6! \cdot P(5,3) = 6! \cdot {5! \over (5-3)!} = 43,200$

Conclusion

A $k$-permutation of $n$ without repetition is calculated as:

$P_{n}^k = {n! \over (n-k)!}$A $k$-permutation of $n$ with repetition is calculated as:

$R_{n}^k = n^k$It is important to note that solving problems about permutations may not always be possible with the above formulas. One strategy for solving such problems is to think of choosing a permutation as a process with a certain number of steps. You can calculate the number of desired permutations by the rule of product.