[Math] Explanation circular permutation

combinatoricspermutations

Well if one looks at the formula of circular permutations $Pc = (n-1)!$

But as we come to that formula, I need a concrete example and an explanation.

Another thing, I have seen that when working with a bracelet, the formula changes. A concrete example please along with an explanation

Finally how the formula is worked when there are repeated elements that are permuted.

Thank you

Best Answer

Circular permutations

Consider an arrangement of blue, cyan, green, yellow, red, and magenta beads in a circle.

For this particular arrangement of the six beads, there are six ways to list the arrangement of the beads in counterclockwise order, depending on whether we start the list with the blue, cyan, green, yellow, red, or magenta bead. They correspond to the six linear arrangements shown in the rows below.

Conversely, each of these six linear arrangements can be transformed into the circular arrangement above by joining the ends of a row.

More generally, any circular arrangement of these six beads corresponds to six linear arrangements. Since there are $6!$ linear arrangements of six distinct beads, the number of distinguishable circular arrangements is $$\frac{6!}{6} = 5!$$

Unless other specified, only the relative order of the objects matters in a circular permutation. Therefore, circular arrangements are considered to be rotationally invariant.

Given a circular arrangement of $n$ objects, they can be rotated $0, 1, 2, \ldots, n - 1$ places clockwise without changing the relative order of the objects. Hence, the number of distinguishable arrangements of $n$ objects in a circle is the number of linear arrangements divided by $n$, which yields $$\frac{n!}{n} = (n - 1)!$$

Alternatively, given $n$ objects, we measure the order relative to a given object. Fix that object. As we proceed counterclockwise around the circle, the remaining objects can be arranged in $(n - 1)!$ orders.

Bracelets

Now suppose we place these beads on a bracelet.

Observe that if you remove the bracelet at left from your wrist, twist it through a half-turn, then place it back on your wrist, it will look like the bracelet at right, where the beads are arranged in the opposite order as you proceed counterclockwise around the circle. Thus, we can form the same bracelet by arranging the blue, cyan, green, yellow, red, and magenta in clockwise or counterclockwise order. Hence, the number of bracelets we can form with the six beads given above is $$\frac{5!}{2}$$

More generally, if a bracelet has no clasp or opening that allows us to distinguish a linear order, it is invariant with respect to both rotations and reflection. Hence, the number of distinguishable arrangements of a bracelet with $n$ objects is $$\frac{1}{2} \frac{n!}{n} = \frac{(n - 1)!}{2}$$ provided $n > 2$. If $n = 1$, there is only one possible arrangement for the bracelet. If $n = 2$, there is only one distinguishable arrangement for the bracelet.

Circular permutations with repetition

This is a much trickier problem. To see why, consider an arrangement of nine blue and three red beads in a circle. Two such arrangements are shown below.

The first time I saw such a problem, I attempted to solve it by choosing three of the $12$ positions for the red beads, then divide by $12$ to account for rotational invariance.
$$\frac{1}{12}\binom{12}{3} = \frac{1}{12} \cdot \frac{12!}{3!9!} = \frac{11!}{3!9!}$$ Alas, this is not an integer. The reason it is not an integer is the arrangement at left. While the circular arrangement at right corresponds to $12$ different linear arrangements, the one at left does not. Given its symmetry, there are only four distinguishable linear arrangements corresponding to the twelve possible starting points of the linear arrangement, depending on whether the first red bead is in the first, second, third, or fourth position of the linear arrangement. Therefore, we have counted this linear arrangement $1/3$ times. Hence, the actual number of circular arrangements is $$\frac{1}{12}\binom{12}{3} + \frac{2}{3}$$

While that observation solves this particular problem, in general, you will need to master the use of Burnside's lemma or the Polya enumeration theorem to handle these problems.