A208772 Number of n-bead necklaces labeled with numbers 1..3 not allowing reversal, with no adjacent beads differing by more than 1.

3, 5, 7, 12, 19, 39, 71, 152, 315, 685, 1479, 3294, 7283, 16359, 36791, 83312, 189123, 431393, 986247, 2262308, 5200851, 11985863, 27676615, 64034954, 148406243, 344507805, 800902879, 1864502926, 4346071603, 10142619039, 23696518919, 55420734752, 129742923475, 304014655205, 712985901943, 1673486556648

Offset

1,1

Comments

Allowing arbitrary differences between the first and last bead gives A215327. [Joerg Arndt, Aug 08 2012]

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 | n } A215335(d). - Joerg Arndt, Aug 13 2012

a(n) = (1/n) * Sum_{d | n} totient(n/d) * A124696(n). - Andrew Howroyd, Mar 18 2017

Example

All solutions for n=4:
..1....2....2....2....1....1....1....3....2....1....2....1
..2....2....3....2....1....2....1....3....3....2....2....1
..1....3....2....2....2....3....1....3....3....2....2....1
..2....3....3....3....2....2....1....3....3....2....2....2

Mathematica

sn[n_, k_] := 1/n*Sum[ Sum[ EulerPhi[j]*(1 + 2*Cos[i*Pi/(k + 1)])^(n/j), {j, Divisors[n]}], {i, 1, k}]; Table[sn[n, 3], {n, 1, 36}] // FullSimplify (* Jean-François Alcover, Oct 31 2017, after Joerg Arndt *)

Prog

(PARI)
/* from the Knopfmacher et al. reference */
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)));
vector(66, n, round(sn(n, 3)) )
/* Joerg Arndt, Aug 09 2012 */

Crossrefs

Column 3 of A208777.

Cf. A215335 (cyclically smooth Lyndon words with 3 colors).

Sequence in context: A241544 A208716 A195821 * A071810 A137576 A161329

Adjacent sequences: A208769 A208770 A208771 * A208773 A208774 A208775

Keyword

nonn

Author

R. H. Hardin, Mar 01 2012

Status

approved