In combinatorics, a *k*-ary **necklace** of length *n* is an equivalence class (a grouping for which there exists an equivalence relation) 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, 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.

## Equivalence classes

### Number of necklaces

There are

different *k*-ary necklaces of length *n*, where * is Euler's totient function.*^{[1]} This follows directly from Pólya's enumeration theorem applied to the action of the cyclic group acting on the set of all functions .
There are also

different necklaces of length *n* with exactly *k* different colored beads, where are the Stirling number of the second kind.

(sequence A054631 in the OEIS) and (sequence A087854 in the OEIS) are related via the Binomial coefficients:

and

### Number of bracelets

There are total

different *k*-ary bracelets of length *n*, where *N*_{k}(*n*) is the number of *k*-ary necklaces of length *n*. This follows from Pólya's method applied to the action of the dihedral group .

## 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*!/2*n*, 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

different *k*-ary aperiodic necklaces of length *n*, where *μ* is the Möbius function. The two necklace-counting functions are related by: where the sum is over all divisors of *n*, which is equivalent by Möbius inversion to

Each aperiodic necklace contains a single Lyndon word so that Lyndon words form representatives of aperiodic necklaces.

## See also

- Lyndon word
- Inversion (discrete mathematics)
- Necklace problem
- Necklace splitting problem
- Permutation
- Proofs of Fermat's little theorem#Proof by counting necklaces
- Forte number, a representation of binary bracelets of length 12 used in atonal music.