A215337 Cyclically smooth Lyndon words with 5 colors.

5, 4, 8, 15, 36, 74, 180, 411, 996, 2400, 5940, 14707, 36972, 93276, 237264, 606030, 1556028, 4009118, 10367892, 26888925, 69930264, 182296212, 476262756, 1246695079, 3269321352, 8587452204, 22590645408, 59510993607, 156973954860, 414552239458, 1096017973380, 2900753084400, 7684758670248, 20377460964156, 54081265456116

Offset: 1

Author

Joerg Arndt, Aug 13 2012

Keywords

• nonn

Comments

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.

Examples

			The cyclically smooth necklaces (N) and Lyndon words (L) of length 4 with 5 colors (using symbols ".", "1", "2", "3", and "4") are:
    ....   1       .  N
    ...1   4    ...1  N L
    ..11   4    ..11  N L
    .1.1   2      .1  N
    .111   4    .111  N L
    .121   4    .121  N L
    1111   1       1  N
    1112   4    1112  N L
    1122   4    1122  N L
    1212   2      12  N
    1222   4    1222  N L
    1232   4    1232  N L
    2222   1       2  N
    2223   4    2223  N L
    2233   4    2233  N L
    2323   2      23  N
    2333   4    2333  N L
    2343   4    2343  N L
    3333   1       3  N
    3334   4    3334  N L
    3344   4    3344  N L
    3434   2      34  N
    3444   4    3444  N L
    4444   1       4  N
There are 24 necklaces (so A208774(4)=24) and a(4)=15 Lyndon words.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..200
• Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.

Programs

Mathematica

terms = 40;
sn[n_, k_] := 1/n Sum[EulerPhi[j] (1+2Cos[i Pi/(k+1)])^(n/j), {i, 1, k}, {j, Divisors[n]}];
vn = Table[Round[sn[n, 5]], {n, terms}];
vl = Table[Sum[MoebiusMu[n/d] vn[[d]], {d, Divisors[n]}], {n, terms}] (* Jean-François Alcover, Jul 22 2018, after Joerg Arndt *)

PARI

default(realprecision,99); /* using floats */
sn(n,k)=1/n*sum(i=1,k,sumdiv(n,j,eulerphi(j)*(1+2*cos(i*Pi/(k+1)))^(n/j)));
vn=vector(66,n, round(sn(n,5)) ); /* necklaces */
/* Lyndon words, via Moebius inversion: */
vl=vector(#vn,n, sumdiv(n,d, moebius(n/d)*vn[d]))

Formula

a(n) = sum_{ d divides n } moebius(n/d) * A208774(d).