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

1, 1, 2, 2, 3, 3, 6, 6, 11, 9, 16, 16, 27, 23, 46, 42, 73, 63, 112, 102, 173, 141, 254, 228, 373, 313, 614, 500, 855, 709, 1252, 1074, 1827, 1457, 2470, 2260, 3559, 2905, 5044, 4294, 6997, 5623, 9752, 8422, 13741, 10913, 18562, 15912, 25213, 20569, 35146, 29286, 46307, 38241, 61396

Offset: 1

Author

Gus Wiseman, May 13 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.

A circular subinterval is a sequence of consecutive indices where the first and last indices are also considered consecutive.

Examples

			The a(1) = 1 through a(10) = 9 necklace compositions (A = 10):
  (1)  (2)  (3)   (4)   (5)   (6)   (7)    (8)    (9)    (A)
            (12)  (13)  (14)  (15)  (16)   (17)   (18)   (19)
                        (23)  (24)  (25)   (26)   (27)   (28)
                                    (34)   (35)   (36)   (37)
                                    (124)  (125)  (45)   (46)
                                    (142)  (152)  (126)  (127)
                                                  (135)  (136)
                                                  (153)  (163)
                                                  (162)  (172)
                                                  (234)
                                                  (243)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..80

Crossrefs

Cf. A000079, A000740, A008965, A108917, A143823, A169942, A276024.

Cf. A325676, A325677, A325678, A325679, A325682, A325683, A325687.

Programs

Mathematica

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
suball[q_]:=Join[Take[q,#]&/@Select[Tuples[Range[Length[q]],2],OrderedQ],Drop[q,#]&/@Select[Tuples[Range[2,Length[q]-1],2],OrderedQ]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&UnsameQ@@Total/@suball[#]&]],{n,15}]

PARI

a(n)={
   my(recurse(k,r,b,w)=
      if(k >= n, 1/r,
         b+=1<Andrew Howroyd, Mar 25 2025

Extensions

a(21) onwards from Andrew Howroyd, Mar 24 2025