A215338 Cyclically smooth Lyndon words with 7 colors.

7, 6, 12, 23, 56, 118, 292, 683, 1692, 4180, 10604, 26978, 69720, 181162, 475072, 1252756, 3324096, 8861054, 23729740, 63786792, 172066648, 465566598, 1263208676, 3435891568, 9366558088, 25585826404, 70019830220, 191943097314, 526978629656, 1448862393216, 3988658225028, 10993822451304, 30335737458872, 83793421017568

Offset

1,1

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.

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.

Formula

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

Example

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:
    ....   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
    3454   4    3454  N L
    4444   1       4  N
    4445   4    4445  N L
    4455   4    4455  N L
    4545   2      45  N
    4555   4    4555  N L
    4565   4    4565  N L
    5555   1       5  N
    5556   4    5556  N L
    5566   4    5566  N L
    5656   2      56  N
    5666   4    5666  N L
    6666   1       6  N
There are 36 necklaces (so A208776(4)=36) and a(4)=23 Lyndon words.

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, 7]], {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 *)

Prog

(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, 7)) ); /* necklaces */
/* Lyndon words, via Moebius inversion: */
vl=vector(#vn, n, sumdiv(n, d, moebius(n/d)*vn[d]))

Crossrefs

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

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

Sequence in context: A281313 A082121 A309622 * A176414 A297153 A363325

Adjacent sequences: A215335 A215336 A215337 * A215339 A215340 A215341

Keyword

nonn

Author

Joerg Arndt, Aug 13 2012

Status

approved