cp's OEIS Frontend

A325681 Number of necklace compositions of n such that every restriction to a circular subinterval has a different sum.

%I A325681 #9 Mar 25 2025 19:19:21
%S A325681 1,1,2,2,3,3,6,6,11,9,16,16,27,23,46,42,73,63,112,102,173,141,254,228,
%T A325681 373,313,614,500,855,709,1252,1074,1827,1457,2470,2260,3559,2905,5044,
%U A325681 4294,6997,5623,9752,8422,13741,10913,18562,15912,25213,20569,35146,29286,46307,38241,61396
%N A325681 Number of necklace compositions of n such that every restriction to a circular subinterval has a different sum.
%C A325681 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 A325681 A circular subinterval is a sequence of consecutive indices where the first and last indices are also considered consecutive.
%H A325681 Andrew Howroyd, <a href="/A325681/b325681.txt">Table of n, a(n) for n = 1..80</a>
%e A325681 The a(1) = 1 through a(10) = 9 necklace compositions (A = 10):
%e A325681   (1)  (2)  (3)   (4)   (5)   (6)   (7)    (8)    (9)    (A)
%e A325681             (12)  (13)  (14)  (15)  (16)   (17)   (18)   (19)
%e A325681                         (23)  (24)  (25)   (26)   (27)   (28)
%e A325681                                     (34)   (35)   (36)   (37)
%e A325681                                     (124)  (125)  (45)   (46)
%e A325681                                     (142)  (152)  (126)  (127)
%e A325681                                                   (135)  (136)
%e A325681                                                   (153)  (163)
%e A325681                                                   (162)  (172)
%e A325681                                                   (234)
%e A325681                                                   (243)
%t A325681 neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
%t A325681 suball[q_]:=Join[Take[q,#]&/@Select[Tuples[Range[Length[q]],2],OrderedQ],Drop[q,#]&/@Select[Tuples[Range[2,Length[q]-1],2],OrderedQ]];
%t A325681 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&UnsameQ@@Total/@suball[#]&]],{n,15}]
%o A325681 (PARI)
%o A325681 a(n)={
%o A325681    my(recurse(k,r,b,w)=
%o A325681       if(k >= n, 1/r,
%o A325681          b+=1<<k;
%o A325681          my(t=bitand((1<<n)-1, bitor(b<<k, b<<(k-n))));
%o A325681          if(k, self()(k+1, r, b-(1<<k), w)) +
%o A325681             if(!bitand(w,t), self()(k+1, r+1, b, w + t));
%o A325681        ));
%o A325681    recurse(0,0,0,0);
%o A325681 } \\ _Andrew Howroyd_, Mar 25 2025
%Y A325681 Cf. A000079, A000740, A008965, A108917, A143823, A169942, A276024.
%Y A325681 Cf. A325676, A325677, A325678, A325679, A325682, A325683, A325687.
%K A325681 nonn
%O A325681 1,3
%A A325681 _Gus Wiseman_, May 13 2019
%E A325681 a(21) onwards from _Andrew Howroyd_, Mar 24 2025