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

1, 1, 1, 3, 3, 5, 5, 13, 13, 27, 21, 41, 41, 77, 63, 143, 129, 241, 203, 385, 347, 617, 491, 947, 835, 1445, 1185, 2511, 1991, 3585, 2915, 5411, 4569, 8063, 6321, 11131, 10133, 16465, 13207, 23817, 20133, 33929, 26663, 48357, 41363, 69605, 54363, 95727, 81183, 132257, 106581

Offset: 0

Author

Gus Wiseman, May 13 2019

Keywords

• nonn

Comments

A composition of n is a finite sequence of positive integers summing to n.

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

For n > 0, a(n) is the number of subsets of Z_n which contain 0 and such that every ordered pair of distinct elements has a different difference (modulo n). The elements of a subset correspond with the partial sums of a composition. For example, when n = 8 the subset {0,2,7} corresponds with the composition (251). - Andrew Howroyd, Mar 24 2025

Examples

			The a(1) = 1 through a(8) = 13 compositions:
  (1)  (2)  (3)   (4)   (5)   (6)   (7)    (8)
            (12)  (13)  (14)  (15)  (16)   (17)
            (21)  (31)  (23)  (24)  (25)   (26)
                        (32)  (42)  (34)   (35)
                        (41)  (51)  (43)   (53)
                                    (52)   (62)
                                    (61)   (71)
                                    (124)  (125)
                                    (142)  (152)
                                    (214)  (215)
                                    (241)  (251)
                                    (412)  (512)
                                    (421)  (521)
		

Links

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

Crossrefs

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

Cf. A325545, A325676, A325677, A325678, A325680, A325681, A325687, A382399.

Programs

Mathematica

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],UnsameQ@@Total/@suball[#]&]],{n,0,15}]

PARI

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

Extensions

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