# Necklace sequences

David W. Wilson wilson at cabletron.com
Mon Aug 17 19:22:42 CEST 1998

```This is a multi-part message in MIME format.
- --------------74F59D632634BE17037BD3B9
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

- --------------74F59D632634BE17037BD3B9
Content-Type: text/plain; charset=us-ascii; name="necklaces"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="necklaces"

I ran a count on 24 different types of black-white necklaces.

The different criteria I used in counting were:

1.  Rotational equivalence.  Necklace indicates rotational equivalence,
string indicates rotational nonequivalence.

2.  Reversal equivalence.  Reversible indicates reversal equivalence.

3.  Complementation equivalence.  Complementable indicates complementation
equivalence.  Complementation equivalence was considered only for
necklaces with an equal number of black and white beads.

4.  Fundamental period.  "with fundamental period n" indicates that only
necklaces with maximal period were counted.

I note that

1.  These sequences were computed by straightforward counting, not by
formula.

2.  Many of the sequences have straightforward formulae.  For
instance, #1 has the formula a(n) = 2^n, while #9 has the
formula choose(2n, n).  In other cases, such as #15, I was able
to come up with a computationally effective recurrence.  Also,
several pairs of sequences are related by the Moebius
transformation.

3.  Some of the sequences below (e.g, #15) are not in Sloane.  Others
(e.g. #20) exist in Sloane and possibly extend the existing sequence.
In many cases, the Sloane sequence description is not terribly
enlightening, though I don't claim that my descriptions are all that
much better.

So, my challenge to seqfan is:

1.  Identify any of the following sequences that already exist in Sloane.

2.  Find formulae or computationally effective recurrences for as many
of the sequences as possible.  I wouldn't be surprised if this could
be done for all of them.  Also, find all pairs related by Moebius
transformations.

3.  Using the formulae found, extend the sequences to full Sloane length.

- ------------------------------------------------------------------------
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304

1,2,3,6,10,20,36,72,136,272,528,1056,2080,4160,8256,16512,32896,65792,131328,262656,524800,1049600,2098176

1,2,3,4,6,8,14,20,36,60,108,188,352,632,1182,2192,4116,7712,14602,27596,52488,99880,190746

1,2,3,4,6,8,13,18,30,46,78,126,224,380,687,1224,2250,4112,7685,14310,27012,50964,96909

5. n-bead black-white strings with fundamental period n.
1,2,2,6,12,30,54,126,240,504,990,2046,4020,8190,16254,32730,65280,131070,261576,524286,1047540,2097018,4192254

6. n-bead black-white reversible strings with fundamental period n.
1,2,1,4,7,18,29,70,126,266,507,1054,2037,4158,8183,16488,32760,65790,131026,262654,524265,1049524,2097119

7. n-bead black-white necklaces with fundamental period n.
1,2,1,2,3,6,9,18,30,56,99,186,335,630,1161,2182,4080,7710,14532,27594,52377,99858,190557

8. n-bead black-white reversible necklaces with fundamental period n.
1,2,1,2,3,6,8,16,24,42,69,124,208,378,668,1214,2220,4110,7630,14308,26931,50944,96782

1,2,6,20,70,252,924,3432,12870,48620,184756,705432

1,1,4,10,38,126,472,1716,6470,24310,92504,352716

1,1,2,4,10,26,80,246,810,2704,9252,32066

1,1,2,3,8,16,50,133,440,1387,4752,16159

13. 2n-bead black-white strings with n black beads and fundamental period 2n.
1,2,4,18,64,250,900,3430,12800,48600,184500,705430

14. 2n-bead black-white reversible strings with n black beads and fundamental period 2n.
1,1,3,9,34,125,459,1715,6432,24300,92375,352715

15. 2n-bead black-white necklaces with n black beads and fundamental period 2n.
1,1,1,3,8,25,75,245,800,2700,9225,32065

16. 2n-bead black-white reversible necklaces with n black beads and fundamental period 2n.
1,1,1,2,6,15,46,132,432,1384,4735,16158

1,1,3,10,35,126,462,1716,6435,24310,92378,352716

1,1,3,7,23,71,252,890,3299,12283,46508,176870

1,1,2,3,7,15,44,128,415,1367,4654,16080

1,1,2,3,7,13,35,85,257,765,2518,8359

21. 2n-bead black-white complementable strings with n black beads and fundamental period 2n.
1,1,2,9,32,125,450,1715,6400,24300,92250,352715

22. 2n-bead black-white reversible complementable strings with n black beads and fundamental period 2n.
1,1,2,6,20,70,243,889,3276,12276,46435,176869

23. 2n-bead black-white complementable necklaces with n black beads and fundamental period 2n.
1,1,1,2,5,14,40,127,408,1364,4638,16079

24. 2n-bead black-white reversible complementable necklaces with n black beads and fundamental period 2n.
1,1,1,2,5,12,31,84,250,762,2504,8358

- --------------74F59D632634BE17037BD3B9--

```