Necklace sequences

[David W. Wilson]

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. n-bead black-white strings.
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304

2. n-bead black-white reversible strings.
1,2,3,6,10,20,36,72,136,272,528,1056,2080,4160,8256,16512,32896,65792,131328,262656,524800,1049600,2098176

3. n-bead black-white necklaces.
1,2,3,4,6,8,14,20,36,60,108,188,352,632,1182,2192,4116,7712,14602,27596,52488,99880,190746

4. n-bead black-white reversible necklaces.
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

9. 2n-bead black-white strings with n black beads.
1,2,6,20,70,252,924,3432,12870,48620,184756,705432

10. 2n-bead black-white reversible strings with n black beads.
1,1,4,10,38,126,472,1716,6470,24310,92504,352716

11. 2n-bead black-white necklaces with n black beads.
1,1,2,4,10,26,80,246,810,2704,9252,32066

12. 2n-bead black-white reversible necklaces with n black beads.
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

17. 2n-bead black-white complementable strings with n black beads.
1,1,3,10,35,126,462,1716,6435,24310,92378,352716

18. 2n-bead black-white reversible complementable strings with n black beads.
1,1,3,7,23,71,252,890,3299,12283,46508,176870

19. 2n-bead black-white complementable necklaces with n black beads.
1,1,2,3,7,15,44,128,415,1367,4654,16080

20. 2n-bead black-white reversible complementable necklaces with n black beads.
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--