info prev up next book cdrom email home

Necklace

\begin{figure}\begin{center}\BoxedEPSF{Necklace.epsf}\end{center}\end{figure}

In the technical Combinatorial sense, an $a$-ary necklace $N(n,a)$ of length $n$ is a string of $n$ characters, each of $a$ possible types. Rotation is ignored, in the sense that $b_1 b_2 \ldots b_n$ is equivalent to $b_k
b_{k+1} \cdots b_n b_1 b_2 \cdots b_{k-1}$ for any $k$, but reversal of strings is respected. Necklaces therefore correspond to circular collections of beads in which the Fixed necklace may not be picked up out of the Plane (so that opposite orientations are not considered equivalent).


The number of distinct Free necklaces $N'(n,a)$ of $n$ beads, each of $a$ possible colors, in which opposite orientations (Mirror Images) are regarded as equivalent (so the necklace can be picked up out of the Plane and flipped over) can be found as follows. Find the Divisors of $n$ and label them $d_1\equiv
1$, $d_2$, ..., $d_\nu(n)\equiv n$ where $\nu(n)$ is the number of Divisors of $n$. Then

\begin{displaymath}
N'(n,a)={1\over 2n}\cases{
\sum_{i=1}^{\nu(n)} \phi(d_i)a^{...
...\over 2}}n(1+a)a^{n/2}\cr
\quad{\rm for\ } n {\rm\ even},\cr}
\end{displaymath}

where $\phi(x)$ is the Totient Function. For $a=2$ and $n=p$ an Odd Prime, this simplifies to

\begin{displaymath}
N'(p,2)={2^{p-1}-1\over p}+2^{(p-1)/2}+1.
\end{displaymath}


\begin{figure}\begin{center}\BoxedEPSF{NecklaceMirror.epsf scaled 950}\end{center}\end{figure}

A table of the first few numbers of necklaces for $a=2$ and $a=3$ follows. Note that $N(n,2)$ is larger than $N'(n,2)$ for $n\geq 6$. For $n=6$, the necklace 110100 is inequivalent to its Mirror Image 0110100, accounting for the difference of 1 between $N(6,2)$ and $N'(6,2)$. Similarly, the two necklaces 0010110 and 0101110 are inequivalent to their reversals, accounting for the difference of 2 between $N(7,2)$ and $N'(7,2)$.

$n$ $N(n,2)$ $N'(n,2)$ $N'(n,3)$
Sloane Sloane's A000031 Sloane's A000029 Sloane's A027671
1 2 2 3
2 3 3 6
3 4 4 10
4 6 6 21
5 8 8 39
6 14 13 92
7 20 18 198
8 36 30 498
9 60 46 1219
10 108 78 3210
11 188 126 8418
12 352 224 22913
13 632 380 62415
14 1182 687 173088
15 2192 1224 481598


Ball and Coxeter (1987) consider the problem of finding the number of distinct arrangements of $n$ people in a ring such that no person has the same two neighbors two or more times. For 8 people, there are 21 such arrangements.

See also Antoine's Necklace, de Bruijn Sequence, Fixed, Free, Irreducible Polynomial, Josephus Problem, Lyndon Word


References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 49-50, 1987.

Dudeney, H. E. Problem 275 in 536 Puzzles & Curious Problems. New York: Scribner, 1967.

Gardner, M. Martin Gardner's New Mathematical Diversions from Scientific American. New York: Simon and Schuster, pp. 240-246, 1966.

Gilbert, E. N. and Riordan, J. ``Symmetry Types of Periodic Sequences.'' Illinois J. Math. 5, 657-665, 1961.

Riordan, J. ``The Combinatorial Significance of a Theorem of Pólya.'' J. SIAM 4, 232-234, 1957.

Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, p. 162, 1980.

Ruskey, F. ``Information on Necklaces, Lyndon Words, de Bruijn Sequences.'' http://sue.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html.

Sloane, N. J. A. Sequences A000029/M0563, A000031/M0564, A001869/M3860, and A027671 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25