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

%I #12 Aug 30 2024 12:05:51

%S 1,2,1,2,3,6,9,18,29,51,82,135,205,315,458,662,925,1281,1724,2305,

%T 3014,3911,4992,6326,7905,9820,12059,14724,17811,21435,25586,30408,

%U 35885,42175,49273,57352,66401,76627,88012,100781,114928,130697,148074,167343,188483,211798,237282,265260,295717,329025,365160

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

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

%F G.f.: (1 + x - 3*x^2 - 2*x^3 + 3*x^4 + 4*x^5-x^6 + 2*x^7 + 9*x^8 + 6*x^9 + 7*x^11 + 12*x^12 + 7*x^13 + 3*x^14 + 6*x^15 + 6*x^16 + x^17-3*x^18 + x^20)/( (-1+x)^6*(1+x)^3*(1-x+x^2)*(1+x+x^2)^2*(1+x+x^2+x^3+x^4) ).

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

%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=6 *)

%Y Cf. A001037 (k arbitrary), A008747 (k<=3), A277619 (k<=4), A277629 (k<=5). 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