A215338 - OEIS

%I #12 Jul 22 2018 10:43:11

%S 7,6,12,23,56,118,292,683,1692,4180,10604,26978,69720,181162,475072,

%T 1252756,3324096,8861054,23729740,63786792,172066648,465566598,

%U 1263208676,3435891568,9366558088,25585826404,70019830220,191943097314,526978629656,1448862393216,3988658225028,10993822451304,30335737458872,83793421017568

%N Cyclically smooth Lyndon words with 7 colors.

%C We call a Lyndon word (x[1],x[2],...,x[n]) smooth if abs(x[k]-x[k-1]) <= 1 for 2<=k<=n, and cyclically smooth if abs(x[1]-x[n]) <= 1.

%H Vincenzo Librandi, <a href="/A215338/b215338.txt">Table of n, a(n) for n = 1..200</a>

%H Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, <a href="http://arxiv.org/abs/0809.0551">Smooth words and Chebyshev polynomials</a>, arXiv:0809.0551v1 [math.CO], 2008.

%F a(n) = sum_{ d divides n } moebius(n/d) * A208776(d).

%e The cyclically smooth necklaces (N) and Lyndon words (L) of length 4 with 7 colors (using symbols ".", "1", "2", "3", "4", "5", and "6") are:

%e     ....   1       .  N

%e     ...1   4    ...1  N L

%e     ..11   4    ..11  N L

%e     .1.1   2      .1  N

%e     .111   4    .111  N L

%e     .121   4    .121  N L

%e     1111   1       1  N

%e     1112   4    1112  N L

%e     1122   4    1122  N L

%e     1212   2      12  N

%e     1222   4    1222  N L

%e     1232   4    1232  N L

%e     2222   1       2  N

%e     2223   4    2223  N L

%e     2233   4    2233  N L

%e     2323   2      23  N

%e     2333   4    2333  N L

%e     2343   4    2343  N L

%e     3333   1       3  N

%e     3334   4    3334  N L

%e     3344   4    3344  N L

%e     3434   2      34  N

%e     3444   4    3444  N L

%e     3454   4    3454  N L

%e     4444   1       4  N

%e     4445   4    4445  N L

%e     4455   4    4455  N L

%e     4545   2      45  N

%e     4555   4    4555  N L

%e     4565   4    4565  N L

%e     5555   1       5  N

%e     5556   4    5556  N L

%e     5566   4    5566  N L

%e     5656   2      56  N

%e     5666   4    5666  N L

%e     6666   1       6  N

%e There are 36 necklaces (so A208776(4)=36) and a(4)=23 Lyndon words.

%t terms = 40;

%t sn[n_, k_] := 1/n Sum[EulerPhi[j] (1+2Cos[i Pi/(k+1)])^(n/j), {i, 1, k}, {j, Divisors[n]}];

%t vn = Table[Round[sn[n, 7]], {n, terms}];

%t vl = Table[Sum[MoebiusMu[n/d] vn[[d]], {d, Divisors[n]}], {n, terms}] (* _Jean-François Alcover_, Jul 22 2018, after _Joerg Arndt_ *)

%o (PARI)

%o default(realprecision,99); /* using floats */

%o sn(n,k)=1/n*sum(i=1,k,sumdiv(n,j,eulerphi(j)*(1+2*cos(i*Pi/(k+1)))^(n/j)));

%o vn=vector(66,n, round(sn(n,7)) ); /* necklaces */

%o /* Lyndon words, via Moebius inversion: */

%o vl=vector(#vn,n, sumdiv(n,d, moebius(n/d)*vn[d]))

%Y Cf. A208776 (cyclically smooth necklaces, 7 colors).

%Y Cf. A215333 (smooth necklaces, 7 colors), A215334 (smooth Lyndon words, 7 colors).

%K nonn

%O 1,1

%A _Joerg Arndt_, Aug 13 2012