Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Necklace (combinatorics)
open-in-new
<p>In <a href="/facts/Combinatorics/k14xUoKT">combinatorics</a>, a <i>k</i>-ary necklace of length <i>n</i> is an <a href="/facts/Equivalence_class/1d2sh0TB">equivalence class</a> of <i>n</i>-character <a href="/facts/String_(computer_science)/4ChJu5WS">strings</a> over an <a href="/facts/Alphabet_(computer_science)/6KW9qYRW">alphabet</a> of size <i>k</i>, taking all <a href="/facts/Circular_shift/noSNJs87">rotations</a> as equivalent. It represents a structure with <i>n</i> circularly connected beads which have <i>k</i> available colors. </p><p>A <i>k</i>-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. </p><p>Formally, one may represent a necklace as an <a href="/facts/Orbit_(group_theory)/Vh9VtUUw">orbit</a> of the <a href="/facts/Cyclic_group/JL5zfFuL">cyclic group</a> <a href="/facts/Group_action_(mathematics)/Vh9VtUUw">acting</a> on <i>n</i>-character strings over an alphabet of size <i>k</i>, and a bracelet as an orbit of the <a href="/facts/Dihedral_group/1PUlRh4M">dihedral group</a>. One can count these orbits, and thus necklaces and bracelets, using <a href="/facts/P%25C3%25B3lya_enumeration_theorem/EBbxaxkz">Pólya's enumeration theorem</a>. </p>