skip to content

In a token ring of n services where only who-follows-whom matters, why does counting every ordering overcount distinct rings n-fold?

level: seniorimportance: nice to knowfreq 28%

answer

  1. a ring has no first element
  2. rotations describe the same ring
  3. groups of equal size divide out
  4. anchor one service instead
  5. distinct labels make orbits equal

basics

~20 s

A ring has no first position, so each ring is written down once for every choice of which service you list first. With n distinct services, those n rotations are all different orderings but the same ring, so the ordering count is n times too large.

solid answer

~50 s

Listing orderings imposes a starting point that the object does not have. Rotating a listing — moving the head to the tail — changes the ordering but leaves every follows-relation intact, so it is the same ring. For `n` distinct services, a ring has exactly `n` rotations and they are all distinct listings, so the listings fall into groups of exactly `n`, one group per ring. Dividing the ordering count by `n` is therefore exact. The equivalent and often clearer move is to **anchor**: fix one service as the head and arrange the remaining `n - 1` freely. Both give the same answer — for six services, `720 / 6 = 120`. The division is licensed by the groups all having the same size, which holds here because the services are distinct; repeated or interchangeable labels break that and the plain division stops being valid.

go deeper

for a junior

Remember that a circular arrangement has no first position, so listing arrangements counts each circle several times over.

for a middle

Explain the grouping argument: listings fall into groups of n rotations, one group per ring, so dividing by n is exact. Show the anchoring alternative gives the same number.

for a senior

Check the precondition before dividing — equal group sizes hold for distinct services but not for interchangeable replicas — and know that a reversible direction changes the factor.

for a principal

Recognise when a reported configuration count is inflated by an undivided symmetry, because a clean factor of error in a design's state-space size distorts every argument built on top of it.

## What 'the same ring' means A token ring is defined by its successor relation: who each service passes the token to. Two descriptions denote the same ring exactly when they induce the same successor relation. A linear listing adds something the ring does not have — a first element — and that extra structure is the entire source of the overcount. Write the same four-service ring starting from each of its members and you get four different listings. Nothing about the ring changed; only where you started reading changed. ## Why dividing by n is exact, not approximate Group the listings by the ring they denote. The argument has three steps, and the third is the one that matters: 1. Every listing denotes exactly one ring, so the groups cover all listings and do not overlap. 2. Every ring is denoted by its `n` rotations, so each group has **at most** `n` members. 3. For `n` **distinct** services, no non-trivial rotation of a listing equals that listing, so each group has **exactly** `n` members. When every group has the same size `n`, the number of groups is the number of listings divided by `n`. That is the whole of the argument, and step 3 is its load-bearing part. Dividing by a symmetry factor is only valid when the symmetry acts the same way on every object. ## Anchoring: the same count without dividing The alternative is to remove the freedom instead of dividing it out. Pick any one service and declare it the head. Every ring now has exactly one listing that starts with that service, so listings and rings correspond one-to-one, and what remains to count is the arrangement of the other `n - 1` services. | Approach | What you count | For 6 distinct services | |---|---|---| | List everything, then divide | all orderings, grouped by rotation | 720 / 6 = 120 | | Anchor one service | arrangements of the remaining 5 | 120 | | List everything, no correction | orderings, treated as rings | 720, which is wrong by a factor of 6 | Anchoring is usually the safer habit in an interview, because it makes the bijection explicit rather than relying on a division whose precondition you then have to defend. ## When the divisor is not n The factor is the number of descriptions of one object, and that is not always `n`. - If the token can travel **either way**, a ring and its reverse are the same ring, so each object has `2n` descriptions rather than `n` — for six services that gives 60 rather than 120. This applies once `n` is at least 3; below that the reversal is not a genuinely different description. - If some services are **interchangeable** — identical replicas with no distinguishing role — different listings can coincide and the groups stop having equal size. Plain division is then invalid, and counting distinct canonical forms is the safe route. - If one position is **already pinned** by the design, for example a fixed coordinator that always holds the token first, there is no rotational freedom left and no division to perform. ## Why this shows up in engineering counting Any arrangement whose identity ignores a starting point has this shape: a rotation schedule over a cycle, a cyclic assignment of shards to replicas, a round-robin ordering. The recurring mistake is not the arithmetic but the claim: reporting the ordering count as though it were the count of genuinely different configurations. That number is too large by a clean factor, and a clean factor is the signature that a symmetry has gone undivided. The habit worth taking away: before counting arrangements, ask what transformation leaves the object unchanged. If one exists, either anchor a position to eliminate it, or divide by the number of forms after checking that every object really has that many.

  • Why is anchoring one service often preferred to dividing by n?
    Anchoring establishes a bijection directly: each ring has exactly one listing beginning with the anchor, so nothing needs correcting afterwards. Division requires first proving every ring has exactly n rotations, which is an extra obligation that is easy to assert and hard to notice failing.
  • What breaks if two of the services in the ring are interchangeable replicas?
    The groups of listings stop being equal in size, because some listings coincide under rotation. Division by n is then no longer exact. Count distinct canonical forms instead — fix a starting rule and compare the resulting descriptions.

A round-robin passing order is fixed by who passes to whom, not by whose name you say first: turning the circle so a different person starts does not change a single hand-off.

saying these in an interview costs you the question

  • Reports the ordering count as the number of distinct rings
  • Divides by a symmetry factor without checking all groups are equal
  • Thinks rotating a ring always produces a genuinely different ring
  • Divides by two for direction even when the token flows one way
  • Believes the division is an approximation rather than exact