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,2

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

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

Example

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

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 *)

Prog

(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

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.

Sequence in context: A341649 A056493 A289352 * A001371 A339408 A277629

Adjacent sequences: A277616 A277617 A277618 * A277620 A277621 A277622

Keyword

nonn,easy

Author

Herbert Kociemba, Oct 24 2016

Status

approved