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

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

Offset: 1

Author

Gus Wiseman, May 11 2019

Keywords

• nonn

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

Examples

			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)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts.

Crossrefs

Cf. A000079, A000740, A008965, A049988, A175342, A325549, A325556, A325558, A325590.

Programs

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}]

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])) )}
w(n,s)={sum(k=1, n, my(R=matrix(n,n,i,j,i==j&&abs(i-k)==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, n-1, w(n,s))} \\ Andrew Howroyd, Aug 24 2019

Extensions

Terms a(26) and beyond from Andrew Howroyd, Aug 24 2019