A328599 - OEIS

A328599

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

1, 0, 0, 0, 0, 2, 0, 4, 2, 4, 12, 8, 22, 14, 36, 44, 62, 114, 130, 206, 264, 414, 602, 822, 1250, 1672, 2520, 3518, 5146, 7408, 10448, 15224, 21496, 31284, 44718, 64170, 92314, 131618, 190084, 271870, 391188, 560978, 804264, 1155976, 1656428, 2381306, 3414846

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

OFFSET

0,6

COMMENTS

A composition of n is a finite sequence of positive integers summing to n.

Circularity means the last part is followed by the first.

LINKS

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

EXAMPLE

The a(0) = 1 through a(12) = 22 compositions (empty columns not shown):

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

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

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

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

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

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

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

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

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

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

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

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

(7,2,3)

(7,3,2)

(2,3,2,5)

(2,3,4,3)

(2,5,2,3)

(3,2,3,4)

(3,2,5,2)

(3,4,3,2)

(4,3,2,3)

(5,2,3,2)

MATHEMATICA

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], And@@Not/@Divisible@@@Partition[#, 2, 1, 1]&&And@@Not/@Divisible@@@Reverse/@Partition[#, 2, 1, 1]&]], {n, 0, 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)={concat([1], sum(k=1, n, b(n, k, (i, j)->i%j<>0&&j%i<>0)))} \\ Andrew Howroyd, Oct 26 2019

CROSSREFS

The necklace version is A328601.

The case forbidding only divisors (not multiples) is A328598.

The non-circular version is A328508.

Partitions with no part followed by a divisor are A328171.