Necklace (combinatorics)

There are 3 bracelets with 3 red and 3 blue beads.
Compare box(6,9) in the triangle.

There are 11 bracelets with 2 red, 2 blue and 2 yellow beads.
Compare box(6,7) in the triangle.

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 of up to k different 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 then 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.

Technically, one may classify a necklace as an orbit of the action of the cyclic group on n-character strings, and a bracelet as an orbit of the dihedral group's action.

Equivalence classes

Number of necklaces

There are

N_{k}(n)={1 \over n}\sum _{d\mid n}\varphi (d)k^{n/d}

different k-ary necklaces of length n, where φ is the Euler's totient function.^[1]

Number of bracelets

There are

B_{k}(n)={\begin{cases}{1 \over 2}N_{k}(n)+{1 \over 4}(k+1)k^{n/2}&{\text{if }}n{\text{ is even}}\\\\{1 \over 2}N_{k}(n)+{1 \over 2}k^{(n+1)/2}&{\text{if }}n{\text{ is odd}}\end{cases}}

different k-ary bracelets of length n, where N_k(n) is the number of k-ary necklaces of length n.

Examples

Necklace example

If there are n beads, all unique, on a necklace joined at the ends, then the number of unique orderings on the necklace, after allowing for rotations, is n!/n, for n > 0. This may also be expressed as (n − 1)!. This number is less than the general case, which lacks the requirement that each bead must be unique.

An intuitive justification for this can be given. If there is a line of n unique objects ("beads"), the number of combinations would be n!. If the ends are joined together, the number of combinations are divided by n, as it is possible to rotate the string of n beads into n positions.

Bracelet example

If there are n beads, all unique, on a bracelet joined at the ends, then the number of unique orderings on the bracelet, after allowing for rotations and reflection, is n!/(2n), for n > 2. Note that this number is less than the general case of B_n(n), which lacks the requirement that each bead must be unique.

To explain this, one may begin with the count for a necklace. This number can be further divided by 2, because it is also possible to flip the bracelet over.

Aperiodic necklaces

An aperiodic necklace of length n is an equivalence class of 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_{k}(n)={1 \over n}\sum _{d\mid n}\mu (d)k^{n/d}

different k-ary aperiodic necklaces of length n, where μ is the Möbius function.

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

Products of Necklaces

The limit of products of the numbers of the fixed necklaces of length n composed of beads of types $N_{k}(n)$ : $N_{k}(n)={1 \over n}\sum _{d\mid n}\varphi (d)k^{n/d}$ :

\lim _{n\to \infty }\prod _{n=1}^{n}N_{k}(n)={\frac {k^{n}}{n!}}1(1+X)(1+X+X^{2})\cdots (1+X+X^{2}+\cdots +X^{n-1}),

,

n\to \infty

,

where the coefficient of $X^{k}$ in the expansion of the product

\prod _{m=1}^{n}\sum _{i=0}^{m-1}X^{i}=1(1+X)(1+X+X^{2})\cdots (1+X+X^{2}+\cdots +X^{n-1})

presents the number of permutations of n with k Inversion (discrete mathematics), it is expressed by a Mahonian number: A008302 (See Gaichenkov link)

References

^ http://mathworld.wolfram.com/Necklace.html

External links

[1] ttp://mathworld.wolfram.com/Necklace.html

[1]