cp's OEIS Frontend

A328601 Number of necklace compositions of n with no part circularly followed by a divisor or a multiple.

%I A328601 #9 Oct 27 2019 05:01:11
%S A328601 0,0,0,0,1,0,2,1,2,5,4,7,6,13,14,20,30,38,50,68,97,132,176,253,328,
%T A328601 470,631,901,1229,1709,2369,3269,4590,6383,8897,12428,17251,24229,
%U A328601 33782,47404,66253,92859,130141,182468,256261,359675,505230,710058,997952,1404214
%N A328601 Number of necklace compositions of n with no part circularly followed by a divisor or a multiple.
%C A328601 A necklace composition of n (A008965) is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.
%C A328601 Circularity means the last part is followed by the first.
%H A328601 Andrew Howroyd, <a href="/A328601/b328601.txt">Table of n, a(n) for n = 1..200</a>
%F A328601 a(n) = A318730(n) - 1.
%e A328601 The a(5) = 1 through a(13) = 6 necklace compositions (empty column not shown):
%e A328601   (2,3)  (2,5)  (3,5)  (2,7)  (3,7)      (2,9)  (5,7)      (4,9)
%e A328601          (3,4)         (4,5)  (4,6)      (3,8)  (2,3,7)    (5,8)
%e A328601                               (2,3,5)    (4,7)  (2,7,3)    (6,7)
%e A328601                               (2,5,3)    (5,6)  (3,4,5)    (2,11)
%e A328601                               (2,3,2,3)         (3,5,4)    (3,10)
%e A328601                                                 (2,3,2,5)  (2,3,5,3)
%e A328601                                                 (2,3,4,3)
%t A328601 neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
%t A328601 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&And@@Not/@Divisible@@@Partition[#,2,1,1]&&And@@Not/@Divisible@@@Reverse/@Partition[#,2,1,1]&]],{n,10}]
%o A328601 (PARI)
%o A328601 b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q,]}
%o A328601 seq(n)={my(v=sum(k=1, n, k*b(n, k, (i,j)->i%j<>0 && j%i<>0))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ _Andrew Howroyd_, Oct 26 2019
%Y A328601 The non-necklace version is A328599.
%Y A328601 The case forbidding divisors only is A328600 or A318729 (with singletons).
%Y A328601 The non-necklace, non-circular version is A328508.
%Y A328601 The version for co-primality (instead of indivisibility) is A328597.
%Y A328601 Cf. A000740, A008965, A032153, A167606, A318748, A328171, A328460, A328593, A328598, A328602, A328603, A328608, A328609.
%K A328601 nonn
%O A328601 1,7
%A A328601 _Gus Wiseman_, Oct 25 2019
%E A328601 Terms a(26) and beyond from _Andrew Howroyd_, Oct 26 2019