A328508 Number of compositions of n with no part divisible by the next or the prior.

1, 1, 1, 1, 1, 3, 1, 6, 4, 8, 14, 14, 27, 30, 55, 69, 97, 155, 200, 312, 421, 630, 893, 1260, 1864, 2600, 3813, 5395, 7801, 11196, 15971, 23126, 32917, 47514, 67993, 97670, 140334, 200913, 289147, 414119, 595109, 853751, 1225086, 1759405, 2523151, 3623984, 5198759

Offset

0,6

Links

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

Example

The a(1) = 1 through a(11) = 14 compositions (A = 10, B = 11):
  (1)  (2)  (3)  (4)  (5)   (6)  (7)    (8)    (9)    (A)     (B)
                      (23)       (25)   (35)   (27)   (37)    (29)
                      (32)       (34)   (53)   (45)   (46)    (38)
                                 (43)   (323)  (54)   (64)    (47)
                                 (52)          (72)   (73)    (56)
                                 (232)         (234)  (235)   (65)
                                               (252)  (253)   (74)
                                               (432)  (325)   (83)
                                                      (343)   (92)
                                                      (352)   (254)
                                                      (523)   (272)
                                                      (532)   (353)
                                                      (2323)  (434)
                                                      (3232)  (452)

Mathematica

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

Prog

(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(i%j && j%i, r[j, k-i])))); concat([1], vecsum(Col(r)))} \\ Andrew Howroyd, Oct 19 2019

Crossrefs

The case of partitions is A328171.

If we only forbid parts to be divisible by the next, we get A328460.

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.

Sequence in context: A193864 A066840 A127754 * A210841 A007383 A206434

Adjacent sequences: A328505 A328506 A328507 * A328509 A328510 A328511

Keyword

nonn

Author

Gus Wiseman, Oct 17 2019

Extensions

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

Status

approved