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

%I #30 Nov 01 2016 12:04:13

%S 1,2,1,2,3,6,8,14,19,28,37,51,64,84,103,129,155,189,222,265,307,359,

%T 411,474,536,611,685,772,859,960,1060,1176,1291,1422,1553,1701,1848,

%U 2014,2179,2363,2547,2751,2954,3179,3403,3649,3895,4164,4432,4725,5017

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

%H Colin Barker, <a href="/A277619/b277619.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-1,-2,-1,2,1,-1).

%F 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)).

%F 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

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

%t (* The g.f. for the number of aperiodic necklaces (Lyndon words) with k<=m black beads and n-k white beads is *)

%t gf[x_,m_]:=Sum[x^i/i Plus@@(MoebiusMu[#](1-x^#)^(-(i/#))&/@Divisors[i]),{i,1,m}]+x+1

%t (* Here we have the case m=4 *)

%o (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

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

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

%K nonn,easy

%O 0,2

%A _Herbert Kociemba_, Oct 24 2016