cp's OEIS Frontend

A328600 Number of necklace compositions of n with no part circularly followed by a divisor.

%I A328600 #8 Oct 27 2019 05:00:20
%S A328600 0,0,0,0,1,0,2,1,3,5,5,7,10,18,20,29,40,58,78,111,156,218,304,429,604,
%T A328600 859,1209,1726,2423,3462,4904,7000,9953,14210,20270,28979,41391,59253,
%U A328600 84799,121539,174162,249931,358577,515090,739932,1063826,1529766,2201382,3168565
%N A328600 Number of necklace compositions of n with no part circularly followed by a divisor.
%C A328600 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 A328600 Circularity means the last part is followed by the first.
%H A328600 Andrew Howroyd, <a href="/A328600/b328600.txt">Table of n, a(n) for n = 1..200</a>
%F A328600 a(n) = A318729(n) - 1.
%e A328600 The a(5) = 1 through a(13) = 18 necklace compositions (empty column not shown):
%e A328600   (2,3)  (2,5)  (3,5)  (2,7)    (3,7)      (2,9)    (5,7)      (4,9)
%e A328600          (3,4)         (4,5)    (4,6)      (3,8)    (2,3,7)    (5,8)
%e A328600                        (2,4,3)  (2,3,5)    (4,7)    (2,7,3)    (6,7)
%e A328600                                 (2,5,3)    (5,6)    (3,4,5)    (2,11)
%e A328600                                 (2,3,2,3)  (2,4,5)  (3,5,4)    (3,10)
%e A328600                                                     (2,3,2,5)  (2,4,7)
%e A328600                                                     (2,3,4,3)  (2,6,5)
%e A328600                                                                (2,8,3)
%e A328600                                                                (3,6,4)
%e A328600                                                                (2,3,5,3)
%t A328600 neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
%t A328600 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&And@@Not/@Divisible@@@Partition[#,2,1,1]&]],{n,10}]
%o A328600 (PARI)
%o A328600 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 A328600 seq(n)={my(v=sum(k=1, n, k*b(n, k, (i,j)->i%j<>0))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ _Andrew Howroyd_, Oct 26 2019
%Y A328600 The non-necklace version is A328598.
%Y A328600 The version with singletons is A318729.
%Y A328600 The case forbidding multiples as well as divisors is A328601.
%Y A328600 The non-necklace, non-circular version is A328460.
%Y A328600 The version for co-primality (instead of divisibility) is A328602.
%Y A328600 Necklace compositions are A008965.
%Y A328600 Partitions with no part followed by a divisor are A328171.
%Y A328600 Cf. A032153, A167606, A318748, A328508, A328593, A328599, A328603, A328608, A328609.
%K A328600 nonn
%O A328600 1,7
%A A328600 _Gus Wiseman_, Oct 25 2019
%E A328600 Terms a(26) and beyond from _Andrew Howroyd_, Oct 26 2019