A328460 Number of compositions of n with no part divisible by the next.

1, 1, 1, 2, 2, 4, 5, 8, 11, 16, 26, 35, 53, 76, 115, 168, 244, 363, 528, 782, 1144, 1685, 2474, 3633, 5347, 7844, 11539, 16946, 24919, 36605, 53782, 79053, 116142, 170700, 250800, 368585, 541610, 795884, 1169572, 1718593, 2525522, 3711134, 5453542, 8013798, 11776138

Offset: 0

Author

Gus Wiseman, Oct 17 2019

Keywords

• nonn

Examples

			The a(1) = 1 through a(9) = 16 compositions:
  (1)  (2)  (3)   (4)   (5)   (6)    (7)    (8)     (9)
            (21)  (31)  (23)  (42)   (25)   (35)    (27)
                        (32)  (51)   (34)   (53)    (45)
                        (41)  (231)  (43)   (62)    (54)
                              (321)  (52)   (71)    (63)
                                     (61)   (251)   (72)
                                     (232)  (323)   (81)
                                     (421)  (341)   (234)
                                            (431)   (252)
                                            (521)   (342)
                                            (2321)  (351)
                                                    (423)
                                                    (432)
                                                    (531)
                                                    (621)
                                                    (3231)
		

Links

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

Crossrefs

The case of partitions is A328171.

If we also require no part to be divisible by the prior, we get A328508.

Compositions with each part relatively prime to the next are A167606.

Compositions with no part relatively prime to the next are A178470.

Cf. A328026, A328028, A328161, A328172, A328189.

Programs

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;Divisible[y,x]]&]],{n,0,10}]

PARI

seq(n)={my(r=matid(n)); for(k=1, n, for(i=1, k-1, r[i,k]=sum(j=1, k-i, if(j%i, r[j, k-i])))); concat([1], vecsum(Col(r)))} \\ Andrew Howroyd, Oct 19 2019

Extensions

Terms a(26) and beyond from Andrew Howroyd, Oct 19 2019