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

6, 11, 16, 30, 52, 117, 242, 577, 1360, 3347, 8278, 20978, 53346, 137422, 355978, 928731, 2434580, 6414014, 16961468, 45017417, 119840582, 319916277, 856089572, 2295950281, 6169664562, 16608996492, 44785220118, 120942143132, 327053057574, 885545659155, 2400570958904, 6514679288762, 17697582670400, 48122529680805

Offset: 1

Author

R. H. Hardin, Mar 01 2012

Keywords

• nonn

Examples

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..100
• Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551 [math.CO], 2008.

Crossrefs

Column 6 of A208777.

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, 6], {n, 1, 34}] // 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,6)) )
/* Joerg Arndt, Aug 09 2012 */

Formula

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