Circular Permutations
Recall from the Permutations of Elements in Sets page that a $k$-permutation of an $n$-element set $A$ is an ordered arrangement of $k$ out of $n$ of the elements.
So far, all of the permutation-related examples we have looked at have been linear permutations in which the order of the elements had somewhat of a "start" and "end" to their ordering. Now let's look at counting the number of permutations that have no "start" or "end".
For example, suppose that we have a set $A = \{ w, x, y, z \}$ and that we want to arrange three of the elements in $A$ on a circle. How many possible ways are there to do this? One might first assume that there are $P(4, 3) = \frac{4!}{(4-3)!} = 24$ ways to do this. Unfortunately, this is the incorrect answer as it over counts the number of ways this can occur.
For example, consider the subset $B \subset A$ given as $B = \{ x, y, z \}$. The arrangement $(x, y, z)$, $(z, x, y)$, and $(y, z, x)$ are all accounted for when placed on a circle due to rotational symmetry as shown below:
In fact, for every circular $3$-permutation there are three linear $3$-permutations that match it. Thus, we can deduce that the total number of circular $3$-permutations is a third the total number of linear $3$-permutations. We generalize this result in the following theorem.
Theorem 1: If $A$ is an $n$-element set then the number of circular $k$-permutations of $A$ is given by $\frac{P(n, k)}{k} = \frac{n!}{k(n-k)!}$. |
- Proof: Let $A = \{ x_1, x_2, ..., x_n \}$. Any linear $k$-permutation of elements from $A$ will be of the form $(x_1, x_2, ..., x_k)$. However, the linear $k$-permutations $(x_k, x_1, x_2, ..., x_{k-1})$, $(x_{k-1}, x_k, x_1, ..., x_{k-2})$, …, [$(x_2, x_3, ..., x_k , x_1)$ are all equivalent when arranged on a circle. For each linear $k$-permutation of elements from $A$ there are thus $\frac{1}{k}$ as many circular $k$-permutations, and so the number of circular $k$-permutations of elements from $A$ is: