The Necklace Sum

Here is a clean fact: the number of subsets of {1, 2, …, n−1} whose elements sum to 0 mod n equals the number of binary necklaces of length n. This has been known. What Dougherty-Bliss and Elizalde show is that requiring the sum to equal r mod n instead of 0 doesn’t change the count — it changes the symmetry. The subsets satisfying the shifted congruence correspond to necklaces with a specific periodicity condition, and the structure of r relative to n determines exactly what that periodicity is.

The through-claim: an additive constraint (sum ≡ r) translates into a geometric constraint (rotational symmetry type). The sum doesn’t care about order; the necklace doesn’t care about magnitude. Yet they count the same objects, and the translation between them preserves more structure than anyone expected — not just the total count but the distribution by subset size matches the distribution by number of ones.

What makes this interesting is the obstruction. The authors prove all their identities using generating functions but note that finding bijective proofs — actually building the map from subsets to necklaces that explains why they match — remains open for most cases. The generating function proves equality without explaining it. The necklace and the sum agree, but nobody can point at a subset and say “this is the necklace it becomes.”

This is a common situation in combinatorics but rarely stated this cleanly: you can prove two sets have the same size by counting both, without ever finding the door between the rooms.