OFFSET
1,9
COMMENTS
A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.
The circular differences of a sequence c of length k are c_{i + 1} - c_i for i < k and c_1 - c_i for i = k. For example, the circular differences of (1,2,1,3) are (1,-1,2,-2).
Up to rotation, a(n) is the number of ways to arrange positive integers summing to n in a circle such that adjacent parts differ by 1 or -1.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
EXAMPLE
The first 16 terms count the following compositions:
3: (12)
5: (23)
6: (1212)
7: (34)
8: (1232)
9: (45)
9: (121212)
10: (2323)
11: (56)
11: (121232)
12: (2343)
12: (12121212)
13: (67)
13: (123232)
14: (3434)
14: (12121232)
15: (78)
15: (123432)
15: (232323)
15: (1212121212)
16: (3454)
16: (12321232)
16: (12123232)
The a(21) = 7 necklace compositions:
(10,11)
(2,3,4,5,4,3)
(3,4,3,4,3,4)
(1,2,1,2,1,2,3,4,3,2)
(1,2,3,2,1,2,3,2,3,2)
(1,2,1,2,3,2,3,2,3,2)
(1,2,1,2,1,2,1,2,1,2,1,2,1,2)
MATHEMATICA
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&(SameQ[1, ##]&@@Abs[Differences[Append[#, First[#]]]])&]], {n, 15}]
PROG
(PARI)
step(R, n, s)={matrix(n, n, i, j, if(i>j, if(j>s, R[i-j, j-s]) + if(j+s<=n, R[i-j, j+s])) )}
a(n)={sum(k=1, n, my(R=matrix(n, n, i, j, i==j&&abs(i-k)==1), t=0, m=1); while(R, R=step(R, n, 1); m++; t+=sumdiv(n, d, R[d, k]*d*eulerphi(n/d))/m ); t/n)} \\ Andrew Howroyd, Aug 23 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 12 2019
EXTENSIONS
a(26)-a(40) from Lars Blomberg, Jun 11 2019
Terms a(41) and beyond from Andrew Howroyd, Aug 23 2019
STATUS
approved