[seqfan] Re: Necklace sequences

[Christian G.Bower]

Dave Wilson wrote:

> I ran a count on 24 different types of black-white necklaces.
...
> 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.

I'll bite
- ------------------------------------------------------------------------
> 1. n-bead black-white strings.
> 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,...
A000079
2^n

> 2. n-bead black-white reversible strings.
> 1,2,3,6,10,20,36,72,136,272,528,1056,2080,4160,...
A005418(n+1)
2^(n-1)+2^(ceiling(n/2)-1)

> 3. n-bead black-white necklaces.
> 1,2,3,4,6,8,14,20,36,60,108,188,352,632,1182,...
A000031
1/n sum{d|n} (phi(n/d)*2^d)

> 4. n-bead black-white reversible necklaces.
> 1,2,3,4,6,8,13,18,30,46,78,126,224,380,687,...
A000029
n odd: 1/2 ([3] + 2^((n+1)/2))
n even: 1/2 ([3] + 2^(n/2-1) + 2^(n/2))

> 5. n-bead black-white strings with fundamental period n.
> 1,2,2,6,12,30,54,126,240,504,990,2046,4020,...
A027375
Moebius of [1]

> 6. n-bead black-white reversible strings with fundamental period n.
> 1,2,1,4,7,18,29,70,126,266,507,1054,2037,...
Not in EIS
Moebius of [2]

> 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,...
A001037
Moebius of [3]

> 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,...
A001371
Moebius of [4]

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

> 10. 2n-bead black-white reversible strings with n black beads.
> 1,1,4,10,38,126,472,1716,6470,24310,92504,352716
A032123(n+1)
n odd: C(2n-1,n-1)
n even: C(2n-1,n-1) + C(n-1,n/2-1)

> 11. 2n-bead black-white necklaces with n black beads.
> 1,1,2,4,10,26,80,246,810,2704,9252,32066
A003239(n+1)
1/n sum{d|n} (phi(n/d)*C(2d-1,d-1))

> 12. 2n-bead black-white reversible necklaces with n black beads.
> 1,1,2,3,8,16,50,133,440,1387,4752,16159
A005648
n odd: 1/2 ([11] + C(n-1,(n-1)/2))
n even: 1/2 ([11] + C(n,n/2))

> 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
A007727
Moebius of [9]

> 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
Not in EIS
Moebius of [10]

> 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
A022553
Moebius of [11]

> 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
Not in EIS
Moebius of [12]

> 17. 2n-bead black-white complementable strings with n black beads.
> 1,1,3,10,35,126,462,1716,6435,24310,92378,352716
A001700(n-1)
[9]/2=C(2n-1,n-1)

> 18. 2n-bead black-white reversible complementable strings with
> n black beads.
> 1,1,3,7,23,71,252,890,3299,12283,46508,176870
A045723
1/2 ([10] + 2^(n-1))

> 19. 2n-bead black-white complementable necklaces with n black beads.
> 1,1,2,3,7,15,44,128,415,1367,4654,16080
Not in EIS
1/2n sum{d|n} (phi(n/d)*C(2d-1,d-1) + phi(2n/d)*2^(d-1))

> 20. 2n-bead black-white reversible complementable necklaces with
> n black beads.
> 1,1,2,3,7,13,35,85,257,765,2518,8359
A006840 (poorly named in EIS)
n odd: 1/2 ([19] + 1/2 C(n-1,(n-1)/2) + 2^(n-2))
n even: 1/2 ([19] + 1/2 C(n,n/2) + 2^(n-2))

> 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
Not in EIS
Moebius of [17]

> 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
Not in EIS
Moebius of [18]

> 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
Not in EIS
Moebius of [19]

> 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
Not in EIS
Moebius of [20]

Another case that might be interesting would be the assymetric versions
of these sequences. Assymetric (identity, without automorphisms) means
that none of the defined symmetries (reversal for a reversible structure,
rotation for a necklace, etc) except the identoty leaves the object
fixed.

All strings are assymetric.
Reversible strings are assymetric if they either have at most one bead
or are not palindromic.

Complementable strings are always assymetric.

Necklaces are assymetric when they are aperiodic (or have fundamental
period n where n is the number of beads).

Reversible necklaces (called bracelets in Frank Ruskey's combinatorial
object server) are assymetric if they are aperiodic and either they
have at most two beads or they are not palindromic.

[1] is its own assymetry
A032085 gives the assymetric version of [2]
[7] is the assymetric version of [3]
A032239 gives the assymetric version of [4]

Another interesting property might be palindromic stings/necklaces.
(Patrick De Geest are you out there?)

Christian


____________________________________________________________________
Get free e-mail and a permanent address at http://www.netaddress.com/?N=1