Motivation
A row of colored positions has distinguished starting and ending points. A necklace forgets its starting position, while a bracelet also forgets which direction it is read. Those changes identify several words with one object, but the number identified is not constant: a monochromatic word has much more symmetry than a generic word.
The correct count averages fixed configurations over the allowed symmetries. We prove why that average counts each orbit exactly once. Rotation cycles then make fixed words easy to count, reflection cycles handle bracelets, and least periods isolate the words whose rotational orbit really does have the full length.
Basic finite group notation is defined as needed.
Definitions
Definition 2.10.1
(Actions, orbits and stabilizers)
A finite group has an associative operation, an identity and an inverse for every element. An action on a finite set assigns a permutation to each group element so that the identity acts identically and .
The orbit of is . Its stabilizer is , and the fixed set of is . Orbits are the equivalence classes obtained by allowing the specified symmetries.
A length- word assigns one of colors to each position indexed modulo , where and is a nonnegative integer. A necklace is an orbit under the rotations. For , a bracelet is an orbit under the permutations generated by rotations and a reflection. A fixed word is constant on every cycle of the position permutation.
The least positive rotation shift fixing a word is its least period . It divides , and the word is a repetition of a length- block. A primitive word has least period . Let be the number of primitive length- words, with the positions still distinguished. Let count residues from zero through coprime to , taking .
Theorem/Proposition
Theorem 2.10.2
(Orbit counting by average fixed sets)
For a finite group action, , and the number of orbits is
No assumption that all orbit sizes are equal is needed. Division by the group order is valid for the fixed-pair sum, rather than for the number of configurations alone.
Theorem 2.10.3
(Necklace and bracelet formulas)
The number of -color necklaces of length is
For , the bracelet count is
where
The color names remain distinguished; no permutation of colors is being factored out.
Theorem 2.10.4
(Primitive periods have a Möbius count)
For every positive ,
Here is the divisor Möbius function developed earlier. Every primitive rotational orbit has exactly words, so the number of primitive necklaces is . All necklaces, including repeated ones, satisfy .
Proof sketch or proof idea
Proof
(Orbit–stabilizer and a double count of fixed pairs)
The orbit relation is reflexive by the identity, symmetric by inverses and transitive by multiplication. Fix a point and consider the map from onto its orbit, sending to . If , then exactly when fixes . Thus the fiber over is and has size . Equal-size fibers give the orbit–stabilizer identity.
Count pairs with . Summing first over gives the fixed-set sum. Summing over gives . On one orbit, the stabilizer identity says every point has stabilizer size divided by that orbit's size, so the orbit contributes exactly . Dividing the pair count by therefore counts the orbits.
Proof X-ray
Count symmetry–configuration pairs before dividing
The proof counts one finite set, the fixed pairs, in two orders, and all the content sits in the second order. There the group structure is used through orbit–stabilizer: the fibers of the map from to are cosets of the stabilizer, so they all have the same size. Consequently every point of an orbit has stabilizer of size the group order divided by the orbit size, and the orbit's total contribution is the group order whatever its size. A highly symmetric word lies in a small orbit but is fixed by more elements; the two effects cancel exactly. That cancellation is the only place unequal orbit sizes are absorbed. Dividing the raw number of words by the number of symmetries skips it, which is why it fails.
The argument explains why different symmetries may have very different fixed sets without invalidating the average.
Rotation cycles determine fixed words
Proof
(Cycle counts for rotations and reflections)
Rotation by positions has cycles. Indeed, the orbit of a position repeatedly adds modulo , and returns for the first time after steps. These equal-length cycles partition the positions. A fixed word independently chooses one color per cycle, giving fixed words.
Group rotation shifts by . Such a shift has the form , with taken modulo and coprime to . There are choices, including the identity shift when . The fixed count is . Summing and applying orbit counting proves the necklace formula, with no enumeration of the orbits themselves.
For reflections, index positions modulo . Every reflection has the form for one of the values of . Its fixed positions solve modulo ; the remaining positions form exchanged pairs.
If is odd, multiplication by two is invertible modulo , so there is exactly one fixed position. Each reflection has position cycles. If is even and is even, there are two fixed positions and hence cycles. If is odd, there are none and hence cycles. Exactly half the reflections have each type. The resulting total fixed counts are precisely . Add the rotation contribution and divide by the group order to prove the bracelet formula.
Least periods justify the primitive partition
Proof
(Least periods, primitive blocks and Möbius inversion)
The shifts fixing a word are closed under addition and negatives modulo . View them instead as integers, including the shift . If is their least positive member, divide any other fixing shift by . Closure makes the remainder a fixing shift; minimality forces zero. In particular divides , and the fixing shifts are exactly the multiples of modulo .
The word is determined by its first positions and repeats them, since shift fixes it. That block is primitive at length : a smaller block period would fix the whole word and contradict minimality. Conversely repeating any primitive block of divisor length gives a length- word with least period exactly . If a smaller shift fixed the repeated word, its residue action on the block would give a smaller block period.
Classify all length- words by this unique divisor . For each such divisor the block choices number , so their sum is . Apply the earlier proved divisor Möbius inversion to obtain the primitive formula. A primitive length- word has trivial rotational stabilizer, so its orbit has size . More generally a word of least period has orbit size , explaining the final all-necklace sum.
Restrictions must be imposed on the fixed configurations
If a prescribed number of positions must carry each color, the same orbit-counting theorem applies, because rotations preserve those counts. However a permutation cycle of length now contributes copies of its chosen color. Its unconstrained choice count cannot simply be reused independently of the totals.
A precise device is to give color a variable . A position cycle of length contributes the polynomial . Multiply these factors over cycles and extract the coefficient of the required color totals. The coefficient counts exactly the fixed words respecting the restriction. Average those coefficients over the group as before. This is a finite polynomial calculation, with no formal convergence issue, and it explains why fixed-content necklaces often require more than inserting a different palette size into the unrestricted formula.
Worked examples
Worked example 2.10.5
(Six binary necklaces of length four have unequal orbit sizes)
The rotation fixed counts are sixteen for the identity, two for a one-step shift, four for a two-step shift and two for a three-step shift. Their average is six. Representatives are .
Their orbit sizes are respectively one, one, four, four, four and two, totaling sixteen words. Dividing sixteen by four would give four, missing the compensation for symmetric configurations. For bracelets at this length the reflection contribution is , so the bracelet count is also six.
Worked example 2.10.6
(Reversal identifies one pair at length six)
For binary length six the rotation sum is , giving fourteen necklaces. Reflection contributions total , giving thirteen bracelets.
The necklaces represented by and are distinct rotational orbits but are related by reversal and a rotation. They therefore become one bracelet. The total count shows that exactly one such pair of necklace orbits is merged; all other necklace orbits are preserved as individual bracelet orbits.
Reversing a rotated word gives a rotation of its reversal. Thus reversal is well-defined on necklaces and applying it twice restores the original class. It either fixes one necklace class or exchanges two, so the decrease from fourteen classes to thirteen proves that exactly one pair was merged.
Worked example 2.10.7
(Primitive binary words and repeated necklaces separate cleanly)
For length six, Möbius inversion gives . Dividing by six gives nine primitive necklaces. The other necklaces have least periods one, two or three.
At those lengths the primitive word counts are two, two and six. Their necklace contributions are two, one and two respectively, totaling five. Adding these five repeated necklaces to the nine primitive ones recovers fourteen. Dividing every length-six word by six would have failed precisely on these shorter orbits.
Concept lensCombinatorial
Symmetry changes the equivalence relation, while period measures its stabilizer
Words, necklaces and bracelets have the same underlying colored positions but different notions of equality. A least period controls rotational orbit size, while reflection can merge two different rotational orbits. The group and permitted color restrictions must be specified before a quotient count has a definite meaning.
Common mistakes
Counterexample mode
The number of configurations need not be divisible by the symmetry group order
There are sixty-four binary words of length six, but the bracelet group has twelve elements. Their quotient is not even an integer, whereas the correct bracelet count is thirteen. The group does not act freely: symmetric words have nontrivial stabilizers. Only a proved free action permits dividing the raw configuration count by the full group order.
The reflection formula is stated for lengths at least three so that the usual distinct polygon symmetries give exactly the specified group.
Common mistake
(Primitive words are not primitive necklaces)
counts words with distinguished positions; each primitive necklace contains exactly of them. For binary length six there are primitive words but primitive necklaces. Reporting as a necklace count, or dividing a non-primitive count by , mixes the two levels.
Common mistake
(Identifying color names without a color action)
The formulas keep color names distinguished: and are different binary necklaces. Treating them as equal is a different problem, with a further action permuting colors, and needs its own orbit count.
Summary
Orbit–stabilizer counting makes the average fixed-set formula exact even with unequal orbit sizes. Rotation and reflection cycles give necklace and bracelet counts. Least periods divide the length and yield a Möbius inversion for primitive words, while fixed-content restrictions are imposed through cycle-weight coefficients before averaging.
Exercises
Quick check
(Count three-color necklaces and bracelets of length three. Also count the primitive necklaces.)
Use the three rotations and three reflections, keeping the color names distinct.
Solution
The rotation sum is , so there are eleven necklaces. Each reflection has two position cycles and fixes nine words; adding their contribution gives bracelets.
At prime length three, only constant words have shorter period. Thus , and the primitive-necklace count is eight. The three remaining necklaces are the monochromatic ones.
Quick check
(Count binary necklaces of length four with exactly two positions of each color. Compute fixed counts rather than using the unrestricted palette formula.)
Inspect the half-turn and note which rotations can preserve the required totals.
Solution
The identity fixes all permitted words. A one-step or three-step rotation fixes only constant words, none of which has two positions of each color. The half-turn has two two-position cycles; assigning different colors to them gives two fixed words. The average is .
Representatives are and . The former has orbit size four and the latter size two, accounting for all six words. The content restriction acts on cycle lengths as well as color choices.
Quick check
(For a prime length and a nonnegative integer , prove combinatorially that divides .)
Separate constant words from primitive words and use their orbit sizes.
Solution · Answer
A least period divides the prime length , so it is either one or . The period-one words are exactly the constant words. Every other word is primitive and belongs to a rotational orbit of size . Therefore is a multiple of . For zero or one color the same statement holds, with the corresponding set empty or entirely constant; no division by a zero configuration count is used.