Necklace (combinatorics)#Aperiodic necklaces

{{main | Necklace polynomial }}

There are

:$N\_k(n)=\backslash frac\{1\}\{n\}\backslash sum\_\{d\backslash mid\; n\}\backslash varphi(d)k^\{n/d\}\; =\; \backslash frac\{1\}\{n\}\; \backslash sum\_\{i=1\}^n\; k^\{\backslash ,\; \{\backslash rm\; gcd\}(i,\; n)\}$

different k-ary necklaces of length n, where $\backslash varphi$ is Euler's totient function.{{MathWorld|id=Necklace|title=Necklace}}

When the beads are restricted to particular color multiset $\backslash mathcal\{B\}\; =\; \backslash \{1^\{n\_1\},\backslash ldots,k^\{n\_k\}\; \backslash \}$, where $n\_i$ is the number of beads of color $i\; \backslash in\; \backslash \{1,\backslash ldots,k\backslash \}$, there are

:$N(\backslash mathcal\{B\})\; =\; \backslash frac\{1\}$

different necklaces made of all the beads of $\backslash mathcal\{B\}$. {{cite web |first=Frank |last=Ruskey |url=http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html |archive-url=https://web.archive.org/web/20061002130346/http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html |archive-date=2006-10-02 |title=Info on necklaces, Lyndon words, De Bruijn sequences |date=2006 }}

Here $|\backslash mathcal\{B\}|\; :=\; \backslash sum\backslash limits\_\{i=1\}^k\; n\_i$ and $\{m\; \backslash choose\; m\_1,\; \backslash 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\; :\; \backslash \{1,\backslash ldots,n\backslash \}\; \backslash to\backslash \{1,\backslash ldots,k\backslash \}$.

If all k colors must be used, the count is

:$L\_k(n)=\backslash frac\{k!\}\{n\}\backslash sum\_\{d\backslash mid\; n\}\backslash varphi(d)S\backslash left(\backslash frac\{n\}\{d\},\; k\backslash right)\backslash ;,$

where $S(n,\; k)$ are the Stirling number of the second kind.

$N\_k(n)$ {{OEIS|A054631}} and $L\_k(n)$ {{OEIS|A087854}} are related via the Binomial coefficients:

:$N\_k(n)=\backslash sum\_\{j=1\}^k\backslash binom\{k\}\{j\}\; L\_j(n)$

and

:$L\_k(n)=\backslash sum\_\{j=1\}^k(-1)^\{k-j\}\backslash binom\{k\}\{j\}N\_j(n)$

The number of different k-ary bracelets of length n {{OEIS|A081720}} is

:$B\_k(n)\; =\; \backslash begin\{cases\}$

\tfrac12 N_k(n) + \tfrac14 (k+1)k^{n/2} & \text{if }n\text{ is even} \\[10px]

\tfrac12 N_k(n) + \tfrac12 k^{(n+1)/2} & \text{if }n\text{ is odd}

\end{cases}\quad,

where N_k(n) 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$.

File:Partition necklaces by integer partition.svg
(set partitions up to rotation and reflection)]]

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 {{sfrac|n!|n}} = (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 {{sfrac|n!|2n}}, 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.

An aperiodic necklace of length n is a rotation equivalence class having 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

:$M\_k(n)=\backslash frac\{1\}\{n\}\backslash sum\_\{d\backslash mid\; n\}\backslash 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\_k(n)\; =\; \backslash sum\_\{d|n\}\; M\_k(d),$ where the sum is over all divisors of n, which is equivalent by Möbius inversion to $M\_k(n)\; =\; \backslash sum\_\{d|n\}\; N\_k(d)\backslash ,\backslash mu\backslash bigl(\backslash tfrac\{n\}\{d\}\backslash bigr).$

Each aperiodic necklace contains a single Lyndon word so that Lyndon words form representatives of aperiodic necklaces.

• 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.

{{reflist}}

• {{Cite book |last1=Polya |first1=Georg |last2=Read |first2=R.C. |last3=Aeppli |first3=Dorothee |title=Combinatorial enumeration of groups, graphs, and chemical compounds |publisher=Springer-Verlag |year=1987 |isbn=9780387964133}}
• {{cite journal |first=Frank |last=Ruskey |first2=Carla |last2=Savage |first3=Terry Min Yih |last3=Wang |title=Generating necklaces |journal=Journal of Algorithms |volume=13 |issue=3 |pages=414–430 |date=1992 |doi=10.1016/0196-6774(92)90047-G |url=}}

Category:Combinatorics on words

Category:Enumerative combinatorics