login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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.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 * A232328 A276229 A077955

Adjacent sequences:  A215333 A215334 A215335 * A215337 A215338 A215339

KEYWORD

nonn

AUTHOR

Joerg Arndt, Aug 13 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 15 14:03 EST 2018. Contains 317239 sequences. (Running on oeis4.)