A277619 Number of aperiodic necklaces (Lyndon words) with k<=4 black beads and n-k white beads.

1, 2, 1, 2, 3, 6, 8, 14, 19, 28, 37, 51, 64, 84, 103, 129, 155, 189, 222, 265, 307, 359, 411, 474, 536, 611, 685, 772, 859, 960, 1060, 1176, 1291, 1422, 1553, 1701, 1848, 2014, 2179, 2363, 2547, 2751, 2954, 3179, 3403, 3649, 3895, 4164, 4432, 4725, 5017

Offset: 0

Author

Herbert Kociemba, Oct 24 2016

Keywords

• nonn
• easy

Examples

			a(6)=8. The aperiodic necklaces are BWWWWW, BBWWWW, BWBWWW, BBBWWW, BBWBWW, BBWWBW, BBBBWW, and BBBWBW.
		

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (1,2,-1,-2,-1,2,1,-1).

Crossrefs

Cf. A001037 (k arbitrary), A008747 (k<=3).

Mathematica section of A032168 gives g.f. for k=m black beads and n-k white beads.

Programs

Mathematica

(* The g.f. for the number of aperiodic necklaces (Lyndon words) with k<=m black beads and n-k white beads is *)
gf[x_,m_]:=Sum[x^i/i Plus@@(MoebiusMu[#](1-x^#)^(-(i/#))&/@Divisors[i]),{i,1,m}]+x+1
(* Here we have the case m=4 *)

PARI

Vec((1+x-3*x^2-2*x^3+3*x^4+5*x^5-3*x^7+x^9)/((-1+x)^4*(1+x)^2*(1+x+x^2)) + O(x^60)) \\ Colin Barker, Oct 29 2016

Formula

G.f.: (1+x-3*x^2-2*x^3+3*x^4+5*x^5-3*x^7+x^9)/((-1+x)^4*(1+x)^2*(1+x+x^2)).

a(n) = a(n-1)+2*a(n-2)-a(n-3)-2*a(n-4)-a(n-5)+2*a(n-6)+a(n-7)-a(n-8) for n>7. - Colin Barker, Oct 29 2016