Necklace (combinatorics)
, so there are 4 necklaces.
≈ 6 min read
Necklace (combinatorics). encyclopegia.org, snapshot enwiki-001364788638. /a/necklace-combinatorics
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
so there are 4 necklaces. Compare box(6,9) in the triangle. , 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, 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.
, so there are 4 necklaces. Compare box(6,9) in the triangle. ]] , 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, 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.
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 \varphi is Euler's totient function. When the beads are restricted to particular color multiset \mathcal{B} = \{1^{n_1},\ldots,k^{n_k} \} , where n_i is the number of beads of color i \in \{1,\ldots,k\} , there are N(\mathcal{B}) = \frac{1} \sum_{d | {\rm gcd}(n_1,\ldots,n_k)} {|\mathcal{B}|/d \choose n_{1}/d, \ldots, n_{k}/d} \phi(d) different necklaces made of all the beads of \mathcal{B} .
Here |\mathcal{B}| := \sum\limits_{i=1}^k n_i and {m \choose m_1, \ldots, m_k} := \frac{m!}{m_1! \cdots m_k!} is the multinomial coefficient. These two formulas follow directly from Pólya's enumeration theorem applied to the action of the cyclic group C_n acting on the set of all functions f : \{1,\ldots,n\} \to\{1,\ldots,k\} .
If all k colors must be used, the count is L_n(k)=\frac{k!}{n}\sum_{d\mid n}\varphi(d)S\left(\frac{n}{d}, k\right)\;, where S(n, k) are the Stirling number of the second kind. N_n(k) and L_n(k) are related via the Binomial coefficients: N_n(k)=\sum_{j=1}^k\binom{k}{j} L_n(j) and L_n(k)=\sum_{j=1}^k(-1)^{k-j}\binom{k}{j}N_n(j) B_n(k) = \begin{cases} \tfrac12 N_n(k) + \tfrac14 (k+1)k^{n/2} & \text{if }n\text{ is even,} \\[10px] \tfrac12 N_n(k) + \tfrac12 k^{(n+1)/2} & \text{if }n\text{ is odd,} \end{cases} where N_n(k) 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 D_n .
For a given set of n beads, all distinct, the number of distinct necklaces made from these beads, counting rotated necklaces as the same, is = (n − 1)!. This is because the beads can be linearly ordered in n! ways, and the n circular shifts of such an ordering all give the same necklace.
Similarly, the number of distinct bracelets, counting rotated and reflected bracelets as the same, is , for n ≥ 3. If the beads are not all distinct, having repeated colors, then there are fewer necklaces (and bracelets). The above necklace-counting polynomials give the number necklaces made from all possible multisets of beads.
Polya's pattern inventory polynomial refines the counting polynomial, using variable for each bead color, so that the coefficient of each monomial counts the number of necklaces on a given multiset of beads. M_n(k)=\frac{1}{n}\sum_{d\mid n}\mu(d)k^{n/d} different k-ary aperiodic necklaces of length n, where μ is the Möbius function.
The two necklace-counting functions are related by: N_n(k) = \sum_{d|n} M_n(k), where the sum is over all divisors of n, which is equivalent by Möbius inversion to M_n(k) = \sum_{d|n} N_d(k)\,\mu\bigl(\tfrac{n}{d}\bigr). Each aperiodic necklace contains a single Lyndon word so that Lyndon words form representatives of aperiodic necklaces.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1364788638 under CC BY-SA 4.0; modifications have been made.