A215335 Cyclically smooth Lyndon words with 3 colors.

3, 2, 4, 7, 16, 30, 68, 140, 308, 664, 1476, 3248, 7280, 16286, 36768, 83160, 189120, 431046, 986244, 2261616, 5200776, 11984382, 27676612, 64031520, 148406224, 344500520, 800902564, 1864486560, 4346071600, 10142581552, 23696518916, 55420651440, 129742921992, 304014466080, 712985901856, 1673486122000

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

Latham Boyle, Paul J. Steinhardt, Self-Similar One-Dimensional Quasilattices, arXiv preprint arXiv:1608.08220 [math-ph], 2016.

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) * A208772(d).

Example

The cyclically smooth necklaces (N) and Lyndon words (L) of length 4 with 3 colors (using symbols ".", "1", and "2") 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
    2222   1       2  N
There are 12 necklaces (so A208772(4)=12) and a(4)=7 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, 3]], {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, 3)) ); /* necklaces */
/* Lyndon words, via Moebius inversion: */
vl=vector(#vn, n, sumdiv(n, d, moebius(n/d)*vn[d]))

Crossrefs

Cf. A208772 (cyclically smooth necklaces, 3 colors).

Cf. A215327 (smooth necklaces, 3 colors), A215328 (smooth Lyndon words, 3 colors).

Sequence in context: A102787 A014193 A128885 * A229976 A084695 A317704

Adjacent sequences: A215332 A215333 A215334 * A215336 A215337 A215338

Keyword

nonn

Author

Joerg Arndt, Aug 13 2012

Status

approved