In combinatorics, a k-ary necklace of length n is an equivalence class of n-character strings over an alphabet of size k, taking all rotations as equivalent. It represents a structure with n circularly connected beads which have k available colors.
A k-ary bracelet, also referred to as a turnover (or free) necklace, is a necklace such that strings may also be equivalent under reflection. That is, given two strings, if each is the reverse of the other, they belong to the same equivalence class. For this reason, a necklace might also be called a fixed necklace to distinguish it from a turnover necklace.
Formally, one may represent a necklace as an orbit of the cyclic group acting on n-character strings over an alphabet of size k, and a bracelet as an orbit of the dihedral group. One can count these orbits, and thus necklaces and bracelets, using Pólya's enumeration theorem.
Contents
Equivalence classes
Number of necklaces
There are
N
n
(
k
)
=
1
n
∑
d
∣
n
φ
(
d
)
k
n
/
d
=
1
n
∑
i
=
1
n
k
g
c
d
(
i
,
n
)
{\displaystyle N_{n}(k)={\frac {1}{n}}\sum _{d\mid n}\varphi (d)k^{n/d}={\frac {1}{n}}\sum _{i=1}^{n}k^{\,{\rm {gcd}}(i,n)}}
Number of bracelets
The number of different k-ary bracelets of length n (sequence A081720 in the OEIS) is
B
n
(
k
)
=
{
1
2
N
n
(
k
)
+
1
4
(
k
+
1
)
k
n
/
2
if
n
is even,
1
2
N
n
(
k
)
Canonicalization
There are many ways to specify a standard rotation of a given k-ary necklace. One of the simplest methods is interpret each letter of the alphabet as a digit in base k and a given rotation as a number in base k. The necklace then be standardized by selecting the rotation that yields the greatest number. The smallest number cannot be chosen because otherwise two necklaces of varying lengths may compare equal due differing numbers of leading zeros not being enough to distinguish between two numbers.
Case of distinct beads
For a given set of n beads, all distinct, the number of distinct necklaces made from these beads, counting rotated necklaces as the same, is n!/n = (n − 1)!. This is because the beads can be linearly ordered in n! ways, and the n circular shifts of such an ordering all give the same necklace. Similarly, the number of distinct bracelets, counting rotated and reflected bracelets as the same, is n!/2n, for n ≥ 3.
If the beads are not all distinct, having repeated colors, then there are fewer necklaces (and bracelets). The above necklace-counting polynomials give the number necklaces made from all possible multisets of beads. Polya's pattern inventory polynomial refines the counting polynomial, using variable for each bead color, so that the coefficient of each monomial counts the number of necklaces on a given multiset of beads.
Aperiodic necklaces
An aperiodic necklace of length n is a rotation equivalence class having size n, i.e., no two distinct rotations of a necklace from such class are equal.
According to Moreau's necklace-counting function, there are
M
n
(
k
)
=
1
n
∑
d
∣
n
μ
(
d
)
k
n
/
d
{\displaystyle M_{n}(k)={\frac {1}{n}}\sum _{d\mid n}\mu (d)k^{n/d}}
different k-ary aperiodic necklaces of length n, where μ is the Möbius function. The two necklace-counting functions are related by:
N
n
(
k
)
=