Necklace (combinatorics)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Possible patterns of bracelets of length n
corresponding to the k-th integer partition
(set partitions up to rotation and reflection)
The 3 bracelets with 3 red and 3 green beads. The one in the middle is chiral, so there are 4 necklaces.
Compare box(6,9) in the triangle.
The 11 bracelets with 2 red, 2 yellow and 2 green beads. The leftmost one and the four rightmost ones are chiral, so there are 16 necklaces.
Compare box(6,7) in the triangle.
16 Tantrix tiles, corresponding to the 16 necklaces with 2 red, 2 yellow and 2 green beads.

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 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.

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[edit]

Number of necklaces[edit]

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 .

Number of bracelets[edit]

There are

different k-ary bracelets of length n, where Nk(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 .

Examples[edit]

Necklace example[edit]

If there are n beads, all distinct, on a necklace joined at the ends, then the number of distinct 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 distinct.

An intuitive justification for this can be given. If there is a line of n distinct 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[edit]

If there are n beads, all distinct, on a bracelet joined at the ends, then the number of distinct 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 Bn(n), which lacks the requirement that each bead must be distinct.

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[edit]

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 equivlent by Möbius inversion to

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


See also[edit]

References[edit]

  1. ^ Weisstein, Eric W. "Necklace". MathWorld.

External links[edit]