A328600 - OEIS

%I #8 Oct 27 2019 05:00:20

%S 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 859,1209,1726,2423,3462,4904,7000,9953,14210,20270,28979,41391,59253,

%U 84799,121539,174162,249931,358577,515090,739932,1063826,1529766,2201382,3168565

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

%C 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 Circularity means the last part is followed by the first.

%H Andrew Howroyd, <a href="/A328600/b328600.txt">Table of n, a(n) for n = 1..200</a>

%F a(n) = A318729(n) - 1.

%e The a(5) = 1 through a(13) = 18 necklace compositions (empty column not shown):

%e   (2,3)  (2,5)  (3,5)  (2,7)    (3,7)      (2,9)    (5,7)      (4,9)

%e          (3,4)         (4,5)    (4,6)      (3,8)    (2,3,7)    (5,8)

%e                        (2,4,3)  (2,3,5)    (4,7)    (2,7,3)    (6,7)

%e                                 (2,5,3)    (5,6)    (3,4,5)    (2,11)

%e                                 (2,3,2,3)  (2,4,5)  (3,5,4)    (3,10)

%e                                                     (2,3,2,5)  (2,4,7)

%e                                                     (2,3,4,3)  (2,6,5)

%e                                                                (2,8,3)

%e                                                                (3,6,4)

%e                                                                (2,3,5,3)

%t neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&And@@Not/@Divisible@@@Partition[#,2,1,1]&]],{n,10}]

%o (PARI)

%o 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 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 The non-necklace version is A328598.

%Y The version with singletons is A318729.

%Y The case forbidding multiples as well as divisors is A328601.

%Y The non-necklace, non-circular version is A328460.

%Y The version for co-primality (instead of divisibility) is A328602.

%Y Necklace compositions are A008965.

%Y Partitions with no part followed by a divisor are A328171.

%Y Cf. A032153, A167606, A318748, A328508, A328593, A328599, A328603, A328608, A328609.

%K nonn

%O 1,7

%A _Gus Wiseman_, Oct 25 2019

%E Terms a(26) and beyond from _Andrew Howroyd_, Oct 26 2019