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. 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--
More information about the SeqFan
mailing list