cp's OEIS Frontend

A325590 Number of necklace compositions of n with circular differences all equal to 1 or -1.

%I A325590 #15 Aug 23 2019 13:36:13
%S A325590 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,
%T A325590 25,32,38,43,53,64,73,89,108,131,153,188,223,272,329,395,475,583,697,
%U A325590 848,1027,1247,1506,1837,2223,2708,3282,3993,4848,5913,7175,8745,10640
%N A325590 Number of necklace compositions of n with circular differences all equal to 1 or -1.
%C A325590 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 A325590 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).
%C A325590 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.
%H A325590 Andrew Howroyd, <a href="/A325590/b325590.txt">Table of n, a(n) for n = 1..200</a>
%e A325590 The first 16 terms count the following compositions:
%e A325590    3: (12)
%e A325590    5: (23)
%e A325590    6: (1212)
%e A325590    7: (34)
%e A325590    8: (1232)
%e A325590    9: (45)
%e A325590    9: (121212)
%e A325590   10: (2323)
%e A325590   11: (56)
%e A325590   11: (121232)
%e A325590   12: (2343)
%e A325590   12: (12121212)
%e A325590   13: (67)
%e A325590   13: (123232)
%e A325590   14: (3434)
%e A325590   14: (12121232)
%e A325590   15: (78)
%e A325590   15: (123432)
%e A325590   15: (232323)
%e A325590   15: (1212121212)
%e A325590   16: (3454)
%e A325590   16: (12321232)
%e A325590   16: (12123232)
%e A325590 The a(21) = 7 necklace compositions:
%e A325590   (10,11)
%e A325590   (2,3,4,5,4,3)
%e A325590   (3,4,3,4,3,4)
%e A325590   (1,2,1,2,1,2,3,4,3,2)
%e A325590   (1,2,3,2,1,2,3,2,3,2)
%e A325590   (1,2,1,2,3,2,3,2,3,2)
%e A325590   (1,2,1,2,1,2,1,2,1,2,1,2,1,2)
%t A325590 neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
%t A325590 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&(SameQ[1,##]&@@Abs[Differences[Append[#,First[#]]]])&]],{n,15}]
%o A325590 (PARI)
%o A325590 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])) )}
%o A325590 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
%Y A325590 Cf. A000079, A000740, A008965, A034297, A173258, A325556, A325588, A325589, A325591.
%K A325590 nonn
%O A325590 1,9
%A A325590 _Gus Wiseman_, May 12 2019
%E A325590 a(26)-a(40) from _Lars Blomberg_, Jun 11 2019
%E A325590 Terms a(41) and beyond from _Andrew Howroyd_, Aug 23 2019