Circular permutation

This sub-section develops the formula for arranging objects around a CIRCLE, rather than in a straight row — a genuinely different counting problem, because a circular arrangement has no fixed starting point.

The core idea: a circular arrangement of $n$ distinct objects can be imagined as being 'cut open' at any one of the $n$ gaps between adjacent objects, and unrolled into a linear (row) arrangement. Crucially, this SAME single circular arrangement can be cut open at any of its $n$ different positions, and each different cut-point produces a DIFFERENT-looking linear arrangement — so one circular arrangement of $n$ objects corresponds to exactly $n$ different linear arrangements (Fig. 3.5 illustrates this for $n=4$).

Let $m$ denote the (unknown, to be found) number of distinct circular arrangements of $n$ objects. Since the total number of LINEAR arrangements of $n$ distinct objects is the familiar $n!$, and each ONE circular arrangement accounts for exactly $n$ of these linear arrangements (one per cut-point), it follows that $m\times n = n!$, so $m = \dfrac{n!}{n} = (n-1)!.$ This is confirmed directly for $n=4$: $m=\dfrac{4!}{4}=3!$. Generalising, the number of circular arrangements of $n$ distinct objects is $(n-1)!$.

Two important Notes refine this basic result. Note 1: a circular arrangement has no fixed starting point, and any ROTATION of a given seating is considered to be the SAME circular arrangement — since every object retains exactly the same left- and right-neighbour after a rotation (Fig. 3.5(a) illustrates several rotated copies of one seating, all counted as a single arrangement). However, CLOCKWISE and ANTICLOCKWISE arrangements ARE still considered different from each other under this basic count (a person's left- and right-hand neighbours genuinely swap if the whole seating is mirror-reversed). A contrasting situation is also noted: if the $n$ positions are themselves FIXED and individually labelled — for example, the four compass directions E, N, W, S, with 4 differently-coloured stickers to be placed on them — then rotating the assignment of stickers to directions produces a genuinely DIFFERENT arrangement (since 'sticker on E' is a fixed, distinguishable position, unlike an unlabelled circular seat). Such a fixed-position arrangement behaves exactly like an ordinary LINEAR arrangement, giving the full $n!$ (not $(n-1)!$) — this is described as an arrangement 'with respect to a round table' (where the individual seats are effectively numbered) as opposed to an arrangement 'with respect to each other' (where only relative neighbour-relationships matter).

Note 2: if clockwise and anticlockwise arrangements are ALSO to be considered the same as each other (as happens physically whenever a circular object like a garland or necklace can be flipped over, e.g. Fig. 3.5(b)) — then each TRUE circular arrangement corresponds to $2n$ different linear arrangements (accounting for both the $n$ cut-points AND the 2 possible reading-directions). So the number of such arrangements is $\dfrac{n!}{2n} = \dfrac{(n-1)!}{2}$.

The sub-section then addresses the case where SOME of the $n$ objects are identical. Theorem: the number of circular arrangements of $n$ objects, of which $m$ objects are identical (indistinguishable from each other), is $\dfrac{(n-1)!}{m!}$. Proof: as argued for the basic case, the $(n-1)!$ circular arrangements would apply if all $n$ objects were distinct; but the $m$ identical objects can be internally rearranged among themselves in $m!$ ways WITHOUT changing the overall circular arrangement (since they are indistinguishable), so the true count must be reduced by this factor: $\dfrac{(n-1)!}{m!}$. (The text notes this argument closely parallels a similar argument encountered earlier — the identical-objects LINEAR permutation formula of §3.5.3.)

A closing Remark covers CIRCULAR permutations of only $r$ objects taken from a larger set of $n$ distinct objects, under two conditions: (a) when clockwise and anticlockwise arrangements are considered different, the count is $\dfrac{{}^nP_r}{r}$; (b) when clockwise and anticlockwise are NOT considered different, the count is $\dfrac{{}^nP_r}{2r}$. (The text invites the reader to verify these two formulas directly for the case $n=6,\ r=3$.)

Solved Example 1. In how many ways can 8 students be arranged at a round table so that 2 particular students are always together, (i) with respect to each other (unnumbered seats), (ii) with respect to the table (numbered seats)? Treating the 2 particular students as a single combined unit leaves 7 'students' to seat. (i) Circular arrangement of these 7 units: $(7-1)!=6!$ ways; the 2 particular students within their combined unit can be arranged in ${}^2P_2=2!$ ways. Total $=6!\times2!=720\times2=1440$. (ii) With numbered seats, the arrangement behaves like a linear one: the 7 units are arranged in $7!$ ways, times $2!$ for the internal pair: $7!\times2!=5040\times2=10080$.

Solved Example 2. In how many ways can 6 men and 3 women be seated at a round table so that every man has a woman beside him (Fig. 3.6)? First seat the 3 women in a circle: $(3-1)!=2!=2$ ways. Once seated, each of the 3 women creates one adjacent position on each side available for a man — giving 6 distinct 'between-women' seat positions in total for the 6 men, who can fill these 6 positions in $6!$ ways. Total $=6!\times2!=720\times2=1440$.

Solved Example 3. Find the number of ways in which 12 different flowers can be arranged in a GARLAND so that 4 particular flowers are always together. Treating the 4 particular flowers as one combined flower leaves 9 flowers to arrange in a garland: $(9-1)!=8!$ ways; the 4 particular flowers within their combined unit can be arranged among themselves in $4!$ ways. Since a garland (unlike an ordinary round-table seating of people) can be turned over, so clockwise and anticlockwise arrangements are considered the same, the raw product $8!\times4!$ must be halved: $\dfrac{1}{2}(8!\times4!) = \dfrac{1}{2}(40320\times24) = 483840$.

Solved Example 4. How many necklaces of 12 beads each can be made from 18 beads of different colours? Here again, clockwise and anticlockwise arrangements of a necklace are the same (it can be flipped over), so — using the Remark's formula (b) for $r$ objects chosen from $n$ — the total number of circular permutations is $\dfrac{{}^{18}P_{12}}{2\times12} = \dfrac{{}^{18}P_{12}}{24}$.

Solved Example 5. Three boys and three girls sit around a table (Fig. 3.7). Boy X does not want any girl as a neighbour, and girl Y does not want any boy as a neighbour. How many distinct arrangements are possible? Under these constraints, X's two neighbours must both be the OTHER two boys ($B_2, B_3$), and Y's two neighbours must both be the OTHER two girls ($G_2, G_3$) — this fixes the overall seating PATTERN, leaving only the freedom to order $B_2, B_3$ on either side of X (2 ways) and to order $G_2, G_3$ on either side of Y (2 ways). Total distinct arrangements $=2\times2=4$.

Solved Example 6. In how many ways can 6 gentlemen and 6 ladies (12 people total) sit around a table, (i) with no restriction, (ii) with no two ladies sitting side by side? (i) Unrestricted circular arrangement of 12 distinct people: $(12-1)!=11!$. (ii) First seat the 6 gentlemen in a circle: $(6-1)!=5!$ ways — this creates exactly 6 gaps (one between each pair of adjacent gentlemen) where a lady could sit so that no two ladies end up adjacent. The 6 ladies then fill these 6 gaps in $6!$ ways. Total $=5!\times6!=120\times720=86400$. …