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

Author

R. H. Hardin, Mar 01 2012

Keywords

• nonn

Comments

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

Examples

			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
		

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.

Crossrefs

Column 3 of A208777.

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

Programs

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 *)

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 */

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