A397417 - OEIS

%I #24 Jul 14 2026 18:35:17

%S 1,1,2,4,8,14,28,51,97,182,346,646,1225,2302,4339,8178,15420,29042,

%T 54743,103163,194417,366391,690493,1301246,2452268,4621483,8709389,

%U 16413334,30931856,58292808,109855920,207029767,390158928,735276156,1385668650,2611369696,4921270577

%N Number of compositions of n in which each pair of adjacent parts is comparable under divisibility (each part divides, or is divided by, the next).

%C 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).

%C 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).

%C Empirically a(n) ~ c*r^n with r ~ 1.8846; no constant-coefficient linear recurrence of order <= 8 fits the data.

%C 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...

%C 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.

%H Alois P. Heinz, <a href="/A397417/b397417.txt">Table of n, a(n) for n = 0..2000</a>

%e 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.

%e 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.

%p b:= proc(n, i) option remember; `if`(n=0, 1, add(`if`(i=0 or

%p       irem(j, i)=0 or irem(i, j)=0, b(n-j, j), 0), j=1..n))

%p     end:

%p a:= n-> b(n, 0):

%p seq(a(n), n=0..36);  # _Alois P. Heinz_, Jul 07 2026

%o (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]}

%o vector(40, n, a(n-1))

%Y Cf. A328508 (no adjacent pair comparable), A328460 (no part divisible by the next), A167606 (each adjacent pair coprime), A178470 (no adjacent pair coprime), A003238 (a(i) | a(i+1) at each step; rooted trees), A000045 (Fibonacci; the parts <= 2 case), A011782.

%K nonn,new

%O 0,3

%A _Oliver Navarro_, Jun 24 2026