Concept 03 / 09Permutations and Combinations
Circular Permutations and Necklaces
Why n distinct objects can be seated in (n - 1)! ways around a table, fixing one object to break the symmetry, necklaces and garlands where clockwise and anticlockwise are the same ((n - 1)!/2), restrictions in circular arrangements, and partial circular selections.
In a circular arrangement there is no first position: only the relative order of the objects matters. Two arrangements are the same if one can be rotated into the other. As the figure shows, each circular arrangement of distinct objects corresponds to different linear arrangements (start reading at any of the positions). Therefore
number of circular arrangements of distinct objects .
An equivalent and more practical view: fix one object in place to remove the rotational freedom, then arrange the remaining objects in the remaining positions relative to it, in ways. Fixing one object is also the best way to handle restrictions.
When are rotations not identified? If the seats are distinguishable (numbered chairs, or a round table with a head seat), the arrangement is effectively linear and the answer is . Always read whether positions are marked.
Necklaces and garlands. If the arrangement can also be flipped over (a necklace of beads, a garland of flowers, a key ring), then clockwise and anticlockwise orders are the same arrangement. Each arrangement then corresponds to circular orders, so the count is for . For people around a table, clockwise and anticlockwise are different (each person's left and right neighbours change), so the division by does not apply. Division by is also incorrect when an arrangement looks the same after flipping (for example, with identical beads); the formula is for distinct objects.
Circular arrangements of some of the objects. Choosing of distinct objects and arranging them in a circle: ways, and for necklaces.
Restrictions work as in the linear case, after fixing one person.
Two particular people always together: treat them as one unit, giving units in a circle, ways, times for the pair's internal order: .
Two particular people never together: .
Alternating arrangements: seat men around a table in ways; this fixes gaps between them, and women fill these gaps in ways, giving . Note that once the men are seated, the gaps are distinguishable, so the women's arrangement is linear.
Specific person between two specific others, or opposite someone: fix the key person and count positions relative to them.
Key Takeaways:
- distinct objects in a circle: ; fix one object and arrange the rest.
- Necklace or garland (flipping allowed), : .
- Numbered seats: linear count .
- out of in a circle: .
- Two people together: ; never together: .
- men and women alternating round a table: .
- Pitfall: dividing by for people round a table. Only arrangements that can be flipped are halved.
Brain-Teaser 1: In how many ways can people sit around a table if two particular people, A and B, must not sit together? What if they must sit exactly opposite each other?
Solution: Total: . Together: . Not together: . For opposite seats, fix A; then B's seat is forced (the seat directly opposite), and the remaining people fill distinguishable seats in ways. Fixing A turns 'opposite' into a single definite seat, which is why fixing one person is the natural first move.
Brain-Teaser 2: How many necklaces can be made from distinct beads? From beads of which are identical red and are distinct?
Solution: With distinct beads: . With two identical red beads, the simple division no longer works, because some arrangements are symmetric. Classify by the positions of the two red beads, which are at circular distance , or apart. For each pattern, place the distinct beads in the other places ( ways), then divide by the number of rotations and reflections that map the pattern of red positions to itself. Distance (adjacent reds): only the identity and the reflection through the axis between the two reds preserve the pattern, so . Distance : the identity and the reflection through the bead between them, so . Distance (opposite reds): the identity, the half-turn, the reflection through both reds and the reflection perpendicular to it, four symmetries, so . Total: necklaces, which a direct computer enumeration confirms. The point is that the formulas and assume distinct objects; with repeated objects, count carefully by cases.
Brain-Teaser 3: men and women sit around a round table alternately. In how many ways can this be done if a particular man M and a particular woman W must not sit next to each other?
Solution: Alternate seatings: fix the men in ways, then the women fill the gaps in ways: . Now count those with W next to M: M has exactly two neighbouring gaps, so W can take of them, and the other women fill the remaining gaps in ways; with men arranged in ways, that gives . So the answer is . After the men are placed, the gaps become distinct labelled spots, and the rest is linear counting.
Practice this concept
Free · no account required · instant solutions