login
A215336
Cyclically smooth Lyndon words with 4 colors.
2
4, 3, 6, 11, 26, 52, 124, 275, 648, 1511, 3618, 8635, 20920, 50758, 124114, 304425, 750330, 1854716, 4600692, 11441298, 28528484, 71290791, 178529666, 447914775, 1125756830, 2833896220, 7144466184, 18036398490, 45591671450, 115381759707, 292329164908, 741410952975, 1882219946418, 4782782372655, 12163730636096
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
Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551 [math.CO], 2008.
FORMULA
a(n) = sum_{ d divides n } moebius(n/d) * A208773(d).
EXAMPLE
The cyclically smooth necklaces (N) and Lyndon words (L) of length 4 with 4 colors (using symbols ".", "1", "2", and "3") 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
3333 1 3 N
There are 18 necklaces (so A208773(4)=24) and a(4)=11 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, 4]], {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, 4)) ); /* necklaces */
/* Lyndon words, via Moebius inversion: */
vl=vector(#vn, n, sumdiv(n, d, moebius(n/d)*vn[d]))
CROSSREFS
Cf. A208773 (cyclically smooth necklaces, 4 colors).
Cf. A215329 (smooth necklaces, 4 colors), A215330 (smooth Lyndon words, 4 colors).
Sequence in context: A196889 A005522 A276202 * A328650 A343891 A232328
KEYWORD
nonn
AUTHOR
Joerg Arndt, Aug 13 2012
STATUS
approved