OFFSET
0,3
COMMENTS
The "divisibility-comparable" member of the family of compositions classified by the divisibility relation between adjacent parts: cf. A167606 (each adjacent pair coprime), A178470 (no adjacent pair coprime), A328460 (no part divisible by the next), and A328508 (no part divisible by the next or prior).
This sequence is the exact positive counterpart of A328508: here every adjacent pair is comparable under divisibility (one part divides the other), whereas in A328508 no adjacent pair is. The stricter chain version requiring a(i) | a(i+1) at every step is A003238 (rooted trees).
Empirically a(n) ~ c*r^n with r ~ 1.8846; no constant-coefficient linear recurrence of order <= 8 fits the data.
Restricted to parts <= 2 the count gives the Fibonacci numbers A000045(n+1); restricted to parts <= k the g.f. is rational, with growth constant increasing from the golden ratio (k=2) toward r ~ 1.8846...
The g.f. satisfies the structural relation A(x) = B(x)/(1 - x*B(x)), where B(x) = Sum_{n>=0} b(n)*x^n counts the same compositions with all parts >= 2 (the part 1 divides everything, so each 1 acts as a universal separator between maximal runs of parts >= 2). This is not a closed form.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..2000
EXAMPLE
a(3) = 4: the compositions of 3 are (3), (1,2), (2,1), (1,1,1); all four qualify since in (1,2) and (2,1) we have 1 | 2.
a(5) = 14: the compositions of 5 that fail are exactly those containing an adjacent pair such as (2,3) or (3,2), since neither 2 | 3 nor 3 | 2.
MAPLE
b:= proc(n, i) option remember; `if`(n=0, 1, add(`if`(i=0 or
irem(j, i)=0 or irem(i, j)=0, b(n-j, j), 0), j=1..n))
end:
a:= n-> b(n, 0):
seq(a(n), n=0..36); # Alois P. Heinz, Jul 07 2026
PROG
(PARI) a(n)={my(f=matrix(n+1, n+1)); for(L=0, n, f[1, L+1]=1); for(rem=1, n, for(L=0, n, my(t=0); for(p=1, rem, if(L==0 || L%p==0 || p%L==0, t+=f[rem-p+1, p+1])); f[rem+1, L+1]=t)); f[n+1, 1]}
vector(40, n, a(n-1))
CROSSREFS
KEYWORD
nonn,new
AUTHOR
Oliver Navarro, Jun 24 2026
STATUS
approved