A383870 Number of compositions of n such that none of the smallest parts are adjacent.

1, 1, 1, 3, 4, 9, 15, 29, 53, 98, 180, 336, 618, 1142, 2110, 3899, 7197, 13283, 24509, 45218, 83396, 153769, 283463, 522449, 962732, 1773742, 3267417, 6018030, 11082693, 20407174, 37572633, 69169726, 127326924, 234362474, 431343281, 793831500, 1460854117

Offset: 0

Author

John Tyler Rascoe, May 13 2025

Keywords

• nonn
• easy

Examples

			a(5) = 9 counts: (1,2,2), (1,3,1), (1,4), (2,1,2), (2,2,1), (2,3), (3,2), (4,1), (5).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2000

Crossrefs

Cf. A003242, A007318, A011782, A074909, A105039, A238342.

Programs

Maple

b:= proc(n, i, p) option remember; `if`(i<1, 0,
     `if`(irem(n, i, 'r')=0, p!*binomial(p+1, r), 0)+
      add(b(n-i*j, min(n-i*j, i-1), p+j)/j!, j=0..n/i))
    end:
a:= n-> `if`(n=0, 1, b(n$2, 0)):
seq(a(n), n=0..36);  # Alois P. Heinz, May 13 2025

PARI

A_x(N) ={Vec(1+sum(j=0,N, sum(i=j+1,N-j, (binomial(i,i-j-1) * x^(j+1) * (x^2/(1-x))^(i-1) )/(1-x^(i+j))))+O('x^N))}
A_x(50)

Formula

G.f.: 1 + Sum_{j>=0} Sum_{i>j} (binomial(i,i-j-1) * x^(j+1) * (x^2/(1 - x))^(i-1))/(1 - x^(i+j)).