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,2

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

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.

Example

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)

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

Prog

(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

Crossrefs

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

Sequence in context: A347700 A049988 A079247 * A244903 A342337 A167932

Adjacent sequences: A325585 A325586 A325587 * A325589 A325590 A325591

Keyword

nonn

Author

Gus Wiseman, May 11 2019

Extensions

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

Status

approved