login
A325590
Number of necklace compositions of n with circular differences all equal to 1 or -1.
6
0, 0, 1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 3, 3, 4, 4, 5, 7, 6, 7, 10, 10, 11, 15, 16, 18, 23, 25, 32, 38, 43, 53, 64, 73, 89, 108, 131, 153, 188, 223, 272, 329, 395, 475, 583, 697, 848, 1027, 1247, 1506, 1837, 2223, 2708, 3282, 3993, 4848, 5913, 7175, 8745, 10640
OFFSET
1,9
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).
Up to rotation, a(n) is the number of ways to arrange positive integers summing to n in a circle such that adjacent parts differ by 1 or -1.
LINKS
EXAMPLE
The first 16 terms count the following compositions:
3: (12)
5: (23)
6: (1212)
7: (34)
8: (1232)
9: (45)
9: (121212)
10: (2323)
11: (56)
11: (121232)
12: (2343)
12: (12121212)
13: (67)
13: (123232)
14: (3434)
14: (12121232)
15: (78)
15: (123432)
15: (232323)
15: (1212121212)
16: (3454)
16: (12321232)
16: (12123232)
The a(21) = 7 necklace compositions:
(10,11)
(2,3,4,5,4,3)
(3,4,3,4,3,4)
(1,2,1,2,1,2,3,4,3,2)
(1,2,3,2,1,2,3,2,3,2)
(1,2,1,2,3,2,3,2,3,2)
(1,2,1,2,1,2,1,2,1,2,1,2,1,2)
MATHEMATICA
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&(SameQ[1, ##]&@@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])) )}
a(n)={sum(k=1, n, my(R=matrix(n, n, i, j, i==j&&abs(i-k)==1), t=0, m=1); while(R, R=step(R, n, 1); m++; t+=sumdiv(n, d, R[d, k]*d*eulerphi(n/d))/m ); t/n)} \\ Andrew Howroyd, Aug 23 2019
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 12 2019
EXTENSIONS
a(26)-a(40) from Lars Blomberg, Jun 11 2019
Terms a(41) and beyond from Andrew Howroyd, Aug 23 2019
STATUS
approved