login
Number of aperiodic necklaces (Lyndon words) with 9 black beads and n white beads.
1

%I #42 Feb 10 2023 18:44:14

%S 0,1,5,18,55,143,333,715,1430,2700,4862,8398,13995,22610,35530,54477,

%T 81719,120175,173583,246675,345345,476901,650325,876525,1168695,

%U 1542684,2017356,2615085,3362260,4289780,5433714,6835972,8544965,10616463,13114465,16112057

%N Number of aperiodic necklaces (Lyndon words) with 9 black beads and n white beads.

%C A row of triangle A051168.

%H Pedro Antonio, <a href="/A263318/b263318.txt">Table of n, a(n) for n = 0..100</a>

%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>

%H <a href="/index/Rec#order_15">Index entries for linear recurrences with constant coefficients</a>, signature (6, -15, 23, -33, 51, -64, 63, -63, 64, -51, 33, -23, 15, -6, 1).

%F a(n) = (1/(n+9))*Sum_{d divides gcd(n+9,9)} mu(d)*binomial((n+9)/d, 9/d).

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

%F G.f.: ((-1+x^3)^-3-(-1+x)^-9)/9. - _Herbert Kociemba_, Oct 16 2016

%t CoefficientList[Series[(x (x^4 - x^3 + 3*x^2 - x + 1))/((x^2 + x + 1)^3 (1 - x)^9), {x, 0, 40}], x] (* _Wesley Ivan Hurt_, Oct 15 2015 *)

%t CoefficientList[Series[((-1+x^3)^-3-(-1+x)^-9)/9,{x,0,40}],x] (* _Herbert Kociemba_, Oct 16 2016 *)

%t LinearRecurrence[{6,-15,23,-33,51,-64,63,-63,64,-51,33,-23,15,-6,1},{0,1,5,18,55,143,333,715,1430,2700,4862,8398,13995,22610,35530},40] (* _Harvey P. Dale_, Feb 10 2023 *)

%o (PARI) a(n)= (1/(n+9))*sumdiv(gcd(n+9,9), d, moebius(d)*binomial( (n+9)/d , 9/d )); \\ _Michel Marcus_, Oct 14 2015

%o (Python)

%o from sympy import mobius, binomial, gcd, divisors

%o print([sum(mobius(d) * binomial((n + 9)//d, 9//d) for d in divisors(gcd(n + 9, 9))) // (n + 9) for n in range(51)]) # _Indranil Ghosh_, Mar 26 2017

%Y Cf. A001840, A006918, A011795, A011796, A011797, A051168.

%K nonn

%O 0,3

%A _Criel Merino_, _Pedro Antonio_, Oct 14 2015

%E More terms from _Michel Marcus_, Oct 14 2015