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, 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 over an alphabet of size k, 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
Number of necklaces
There are
N n ( k ) = 1 n ∑ d ∣ n φ ( d ) k n / d = 1 n ∑ i = 1 n k g c d ( i , n ) {\displaystyle N_{n}(k)={\frac {1}{n}}\sum _{d\mid n}\varphi (d)k^{n/d}={\frac {1}{n}}\sum _{i=1}^{n}k^{\,{\rm {gcd}}(i,n)}}
different k-ary necklaces of length n, where φ {\displaystyle \varphi } is Euler's totient function. When the beads are restricted to particular color multiset B = { 1 n 1 , … , k n k } {\displaystyle {\mathcal {B}}=\{1^{n_{1}},\ldots ,k^{n_{k}}\}} , where n i {\displaystyle n_{i}} is the number of beads of color i ∈ { 1 , … , k } {\displaystyle i\in \{1,\ldots ,k\}} , there are
N ( B ) = 1 | B | ∑ d | g c d ( n 1 , … , n k ) ( | B | / d n 1 / d , … , n k / d ) ϕ ( d ) {\displaystyle N({\mathcal {B}})={\frac {1}{|{\mathcal {B}}|}}\sum _{d|{\rm {gcd}}(n_{1},\ldots ,n_{k})}{|{\mathcal {B}}|/d \choose n_{1}/d,\ldots ,n_{k}/d}\phi (d)}
… excerpt ends here. Continue reading the full article.
