Explanation circular permutation

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

Solution 1:

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.

Solution 2:

both arguments are from the book:Combinatorics by AlirezaAlipoor.

Think of $n$ distinct object around a round table.

We call them $a_1,a_2,a_3...,a_n$.

if we put one in a certain position,say we put $a_1$ on the top of the table, then the others can permute linearly,Thus the number of permutation is $$(n-1)!$$.

Second argument: Consider the previous setup,and we let our objects permute linearly,

which can be done in $n!$ different ways.

BUT,if we have our table rotated such that:$a_1 \to a_2 , a_2\to a_3,... a_n \to a_1$then we have found a permutation that is the same configuration around our table.

Observe that we can do this rotation in $n$ many ways,since we can rotate $n$ times clock-wise and still have the same configuration.

therefore if we let $x$ be the number of $ distinct$ permutations,

if we multiply it by $n$ , the number of rotations , we should get the number of Linear permutations,$n!$: $$ nx = n!$$ $$x = \frac {n!}{n}$$

$$x = (n-1)!$$

Solution 3:

The table in the big conference room at the Hall of Justice is shaped like a horseshoe. How many ways can we seat the Superfiends (Batman, Superman, Wonderwoman, Aquaman) around this table. $4!$

The small conference room has a circular table. Furthermore the door is invisible. We do not distinguish who is at the head of the table (there is no head) or at an end of the table. In order to count the possibilities, we fix Superman's (Superman was chosen arbitrarily) position, and discuss all seating arrangements relative to Superman. There are $3!$ ways to seat the table (one of 3 people sit Supe's left, once that person is seated, one of 2 remaining can sit at his right, and one the last person across.)