Necklace (combinatorics)
Encyclopedia
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.
different k-ary necklaces of length n, where φ is the Euler's totient function
.
different k-ary bracelets of length n, where Nk(n) is the number of k-ary necklaces of length n.
! . 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.
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.
According to Moreau's necklace-counting function, there are
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.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, a k-ary necklace of length n is an equivalence class of n-character strings over an alphabet of size k, taking all rotations
Circular shift
In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation...
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
Group action
In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
of the cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
on n-character strings, and a bracelet as an orbit of the dihedral group
Dihedral group
In mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...
's action.
Number of necklaces
There aredifferent k-ary necklaces of length n, where φ is the Euler's totient function
Euler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...
.
Number of bracelets
There aredifferent k-ary bracelets of length n, where Nk(n) is the number of k-ary necklaces of length n.
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)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 Bn(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
different k-ary aperiodic necklaces of length n, where μ is the Möbius function
Möbius function
The classical Möbius function μ is an important multiplicative function in number theory and combinatorics. The German mathematician August Ferdinand Möbius introduced it in 1832...
.
Each aperiodic necklace contains a single Lyndon word
Lyndon word
In mathematics, in the areas of combinatorics and computer science, a Lyndon word is a string that is strictly smaller in lexicographic order than all of its rotations...
so that Lyndon words form representatives of aperiodic necklaces.
See also
- Lyndon wordLyndon wordIn mathematics, in the areas of combinatorics and computer science, a Lyndon word is a string that is strictly smaller in lexicographic order than all of its rotations...
- Necklace problemNecklace problemThe necklace problem is a problem in recreational mathematics, solved in the early 21st century.- Formulation :Suppose that a person you are in contact with has a necklace of n beads, each of which is either black or white. You wish to identify the order in which the n beads go around the...
- Necklace splitting problemNecklace splitting problemIn mathematics, and in particular combinatorics, the necklace splitting problem arises in a variety of contexts including exact division; its picturesque name is due to mathematicians Noga Alon and Douglas B. West....
- Proofs of Fermat's little theorem#Proof by counting necklaces