<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 3" %>
Decomposition of Necklaces
William Y.C.Chen1and Jun Wang2
1Center for Combinatorics, The Key Laboratory of Pure Mathematics and Combinatorics of Ministry of Education, Nankai University, Tianjin 300071, P.R. China
2Department of Applied Mathematics, Dalian University of Technology, Dalian 116024, P.R. China
Annals of Combinatorics 5 (3) p.271-283 September, 2001
AMS Subject Classification: 05A05, 68R15
This work originates from a combinatorial understanding of a branching property of MSS (Metropolis-Stein-Stein) sequences in symbolic dynamics. It is known that MSS sequences are in one-to-one correspondence with equivalence classes of primitive necklaces on two colors under the exchange of colors. We present a branching property of primitive self-complementary necklaces, leading to a combinatorial explanation of an analogous property of MSS sequences.
Keywords: necklaces, MSS sequences, symbolic dynamics, discrete dynamical systems


1.  W.A. Beyer, R.D. Mauldin, and P.R. Stein, Shift-maximal sequences in function iteration: existence, uniqueness, and multiplicity, J. Math. Anal. Appl. 115 (1986) 305每362.

2.  B.L. Bivins, J.D. Louck, N. Metropolis, and M.L. Stein, Classification of all cycles of the parabolic map, Physica D 51 (1991) 3每27.

3.  K.M. Brucks, MSS sequences, coloring of necklaces, and periodic points of f (z) = z2 -2, Adv. Appl. Math. 8 (1987) 434每445.

4.  W.Y.C. Chen and J.D. Louck, Necklaces, MSS sequences and DNA sequences, Adv. Appl. Math. 18 (1997) 18每32.

5.  P. Collet and J.-P. Eckmann, Iterated Maps on the Interval as Dynamical Systems, Birkhäuser, Boston, 1980.

6.  B.L. Hao, Elementary Symbolic Dynamics and Chaos in Dissipative Systems, World Scientific, Singapore, 1989.

7.  M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and Its Applications 17, G.-C. Rota, Ed., Addison-Wesley, Reading, 1983.

8.  J.D. Louck, Problems in combinatorics on words originating from discrete systems, Ann. Combin. 1 (1997) 99每104.

9.  J.D. Louck and N. Metropolis, Symbolic Dynamics of Trapezoidal Maps, Reidel, Dordrecht, 1986.

10.  N. Metropolis, M.L. Stein, and P.R. Stein, On finite limit sets for transformations on the unit interval, J. Combin. Theory Ser. A 15 (1973) 25每44.

11.  G.-C. Rota, B. Sagan, and P.R. Stein, A cyclic derivative in noncommutative algebra, J. Algebra 64 (1980) 54每75.

12.  L. Sun and G. Helmberg, Maximal words connected with unimodal maps, Order 4 (1988) 351每380.