cp's OEIS Frontend

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

%I A325588 #11 Aug 24 2019 11:51:24
%S A325588 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,
%T A325588 36,56,33,59,43,86,64,74,76,136,95,127,138,219,178,245,249,372,370,
%U A325588 445,506,747,730,907,1069,1431,1544,1927,2268,2981,3332,4074,4896,6320
%N A325588 Number of necklace compositions of n with equal circular differences up to sign.
%C A325588 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.
%C A325588 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).
%H A325588 Andrew Howroyd, <a href="/A325588/b325588.txt">Table of n, a(n) for n = 1..200</a>
%H A325588 Gus Wiseman, <a href="/A325325/a325325.txt">Sequences counting and ranking integer partitions by the differences of their successive parts.</a>
%e A325588 The a(1) = 1 through a(8) = 9 compositions:
%e A325588   (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
%e A325588        (11)  (12)   (13)    (14)     (15)      (16)       (17)
%e A325588              (111)  (22)    (23)     (24)      (25)       (26)
%e A325588                     (1111)  (11111)  (33)      (34)       (35)
%e A325588                                      (222)     (1111111)  (44)
%e A325588                                      (1212)               (1232)
%e A325588                                      (111111)             (1313)
%e A325588                                                           (2222)
%e A325588                                                           (11111111)
%t A325588 neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
%t A325588 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&SameQ@@Abs[Differences[Append[#,First[#]]]]&]],{n,15}]
%o A325588 (PARI)
%o A325588 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])) )}
%o A325588 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)}
%o A325588 a(n) = {numdiv(max(1,n)) + sum(s=1, n-1, w(n,s))} \\ _Andrew Howroyd_, Aug 24 2019
%Y A325588 Cf. A000079, A000740, A008965, A049988, A175342, A325549, A325556, A325558, A325590.
%K A325588 nonn
%O A325588 1,2
%A A325588 _Gus Wiseman_, May 11 2019
%E A325588 Terms a(26) and beyond from _Andrew Howroyd_, Aug 24 2019