A328601 - OEIS

A328601

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

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, 470, 631, 901, 1229, 1709, 2369, 3269, 4590, 6383, 8897, 12428, 17251, 24229, 33782, 47404, 66253, 92859, 130141, 182468, 256261, 359675, 505230, 710058, 997952, 1404214

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,7

COMMENTS

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.

Circularity means the last part is followed by the first.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..200

FORMULA

a(n) = A318730(n) - 1.

EXAMPLE

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

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

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

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

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

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

(2,3,2,5) (2,3,5,3)

(2,3,4,3)

MATHEMATICA

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

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}]

PROG

(PARI)

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, ]}

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

CROSSREFS

The non-necklace version is A328599.

The case forbidding divisors only is A328600 or A318729 (with singletons).

The non-necklace, non-circular version is A328508.

The version for co-primality (instead of indivisibility) is A328597.