From Wikipedia, the free 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. This enables application
of Pólya enumeration theorem for
enumeration of necklaces and bracelets.
1 Equivalence classes
Possible patterns of bracelets of length n
1.1 Number of necklaces
corresponding to the k-th integer partition
1.2 Number of bracelets
(set partitions up to rotation and reflection)
2 Examples
2.1 Necklace example
2.2 Bracelet example
3 Aperiodic necklaces
4 Products of necklaces
5 See also
6 References
7 External links
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.
Number of necklaces
There are
different k-ary necklaces of length n, where φ is Euler's
totient function.[1] The 11 bracelets with 2 red, 2 yellow and 2 green
beads. The leftmost one and the four rightmost ones
Number of bracelets are chiral, so there are 16 necklaces.
Compare box(6,7) in the triangle.
There are
16 Tantrix tiles, corresponding to the 16 necklaces
with 2 red, 2 yellow and 2 green beads.
different 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 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
If there are n beads, all distinct, on a bracelet joined at the ends, then the number of distinct orderings on the
n!
bracelet, after allowing for rotations and reflection, is 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.
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.
Each aperiodic necklace contains a single Lyndon word so that Lyndon words form representatives of
aperiodic necklaces.
The limit of the product of the numbers of fixed necklaces of length n composed of k types of beads:
where the coefficient of Xk in the expansion of the product
presents the number of permutations of n with k inversions, expressed by a Mahonian number: A008302
(See Gaichenkov link)
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.
1. Weisstein, Eric W. "Necklace". MathWorld.
Weisstein, Eric W. "Necklace". MathWorld.
Info on necklaces, Lyndon words, De Bruijn sequences (http://www.theory.csc.uvic.ca/~cos/inf
/neck/NecklaceInfo.html)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Necklace_(combinatorics)&oldid=767219408"
Categories: Combinatorics on words Enumerative combinatorics
This page was last modified on 24 February 2017, at 16:21.
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may
apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered
trademark of the Wikimedia Foundation, Inc., a non-profit organization.
