A330620 Number of length n necklaces with entries covering an initial interval of positive integers and no adjacent entries equal.

0, 1, 2, 10, 54, 392, 3378, 34120, 393738, 5112406, 73756026, 1170482186, 20263782630, 380047964920, 7676106365966, 166114208828980, 3834434324386350, 94042629535109500, 2442147034719168714, 66942194906112161302, 1931543452345335094678, 58519191359163454708564

Offset: 1

Author

Andrew Howroyd, Dec 20 2019

Keywords

• nonn

Examples

			Case n=4: there are the following 10 necklaces:
  1212,
  1213, 1232, 1323,
  1234, 1243, 1324, 1342, 1423, 1432.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200

Crossrefs

Row sums of A330618.

Cf. A019536, A208535.

Programs

PARI

\\ here U(n, k) is A208535(n, k) for n > 1.
U(n, k)={sumdiv(n, d, eulerphi(n/d)*(k-1)^d)/n - if(n%2, k-1)}
a(n)={if(n<1, n==0, sum(j=1, n, U(n,j)*sum(k=j, n, (-1)^(k-j)*binomial(k, j))))}