A328598 - OEIS

%I #10 Oct 27 2019 04:58:26

%S 1,0,0,0,0,2,0,4,2,7,12,11,22,26,55,63,99,149,215,324,458,699,1006,

%T 1492,2185,3202,4734,6928,10242,14951,22023,32365,47557,69905,102633,

%U 150983,221712,325918,478841,703647,1034103,1519431,2233061,3281003,4821790,7085358

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

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

%C Circularity means the last part is followed by the first.

%H Andrew Howroyd, <a href="/A328598/b328598.txt">Table of n, a(n) for n = 0..200</a>

%F a(n > 0) = A318726(n) - 1.

%e The a(5) = 2 through a(12) = 22 compositions (empty column not shown):

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

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

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

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

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

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

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

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

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

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

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

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

%e                                                     (7,2,3)

%e                                                     (7,3,2)

%e                                                     (2,3,2,5)

%e                                                     (2,3,4,3)

%e                                                     (2,5,2,3)

%e                                                     (3,2,3,4)

%e                                                     (3,2,5,2)

%e                                                     (3,4,3,2)

%e                                                     (4,3,2,3)

%e                                                     (5,2,3,2)

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

%Y The necklace version is A328600, or A318729 without singletons.

%Y The version with singletons is A318726.

%Y The non-circular version is A328460.

%Y Also forbidding parts circularly followed by a multiple gives A328599.

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

%Y Cf. A000740, A008965, A167606, A178470, A318748, A328187, A328508, A328593, A328597, A328601, A328603, A328609.

%K nonn

%O 0,6

%A _Gus Wiseman_, Oct 24 2019

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