

A325588


Number of necklace compositions of n with equal circular differences up to sign.


4



1, 2, 3, 4, 4, 7, 5, 9, 8, 10, 8, 17, 9, 14, 15, 22, 12, 23, 14, 31, 23, 25, 19, 48, 25, 35, 36, 56, 33, 59, 43, 86, 64, 74, 76, 136, 95, 127, 138, 219, 178, 245, 249, 372, 370, 445, 506, 747, 730, 907, 1069, 1431, 1544, 1927, 2268, 2981, 3332, 4074, 4896, 6320
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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


LINKS



EXAMPLE

The a(1) = 1 through a(8) = 9 compositions:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (12) (13) (14) (15) (16) (17)
(111) (22) (23) (24) (25) (26)
(1111) (11111) (33) (34) (35)
(222) (1111111) (44)
(1212) (1232)
(111111) (1313)
(2222)
(11111111)


MATHEMATICA

neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&SameQ@@Abs[Differences[Append[#, First[#]]]]&]], {n, 15}]


PROG

(PARI)
step(R, n, s)={matrix(n, n, i, j, if(i>j, if(j>s, R[ij, js]) + if(j+s<=n, R[ij, j+s])) )}
w(n, s)={sum(k=1, n, my(R=matrix(n, n, i, j, i==j&&abs(ik)==s), t=0, m=1); while(R, R=step(R, n, s); m++; t+=sumdiv(n, d, R[d, k]*d*eulerphi(n/d))/m ); t/n)}
a(n) = {numdiv(max(1, n)) + sum(s=1, n1, w(n, s))} \\ Andrew Howroyd, Aug 24 2019


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



