TOPICS
Search

Necklace


Necklace

In the technical combinatorial sense, an a-ary necklace of length n is a string of n characters, each of a possible types. Rotation is ignored, in the sense that b_1b_2...b_n is equivalent to b_kb_(k+1)...b_nb_1b_2...b_(k-1) for any k.

In fixed necklaces, reversal of strings is respected, so they represent circular collections of beads in which the necklace may not be picked up out of the plane (i.e., opposite orientations are not considered equivalent). The number of fixed necklaces of length n composed of a types of beads N(n,a) is given by

 N(n,a)=1/nsum_(i=1)^(nu(n))phi(d_i)a^(n/d_i),
(1)

where d_i are the divisors of n with d_1=1, d_2, ..., d_nu(n)=n, nu(n) is the number of divisors of n, and phi(x) is the totient function.

For free necklaces, opposite orientations (mirror images) are regarded as equivalent, so the necklace can be picked up out of the plane and flipped over. The number N^'(n,a) of such necklaces composed of n beads, each of a possible colors, is given by

 N^'(n,a)=1/(2n){sum_(i=1)^(nu(n))phi(d_i)a^(n/d_i)+na^((n+1)/2)   for n odd; sum_(i=1)^(nu(n))phi(d_i)a^(n/d_i)+1/2n(1+a)a^(n/2)   for n even.
(2)

For a=2 and n=p an odd prime, this simplifies to

 N^'(p,2)=(2^(p-1)-1)/p+2^((p-1)/2)+1.
(3)
NecklaceMirror

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>=6. For n=6, the necklace 110100 is inequivalent to its mirror image 001011, 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).

nN(n,2)N^'(n,2)N^'(n,3)
SloaneA000031A000029A027671
1223
2336
34410
46621
58839
6141392
72018198
83630498
960461219
10108783210
111881268418
1235222422913
1363238062415
141182687173088
1521921224481598

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

Explore with Wolfram|Alpha

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://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html.Skiena, S. "Polya's Theory of Counting." §1.2.6 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 25-26, 1990.Sloane, N. J. A. Sequences A000029/M0563, A000031/M0564, A001869/M3860, and A027671 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Necklace

Cite this as:

Weisstein, Eric W. "Necklace." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Necklace.html

Subject classifications