A383253 Number of compositions of n with parts in standard order.

1, 1, 1, 2, 3, 5, 9, 16, 29, 53, 98, 182, 340, 638, 1202, 2273, 4312, 8204, 15650, 29925, 57344, 110101, 211771, 407987, 787174, 1520851, 2942030, 5697842, 11046881, 21438881, 41645541, 80967881, 157547508, 306791828, 597847686, 1165828440, 2274890125

Offset: 0

Author

John Tyler Rascoe, May 06 2025

Keywords

• nonn
• easy

Comments

A composition with parts in standard order satisfies the condition that for any part p > 1, the part p - 1 has already appeared. All compositions of this kind have first part 1.

Examples

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

Links

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

Crossrefs

Cf. A000110, A011782, A047998, A107429, A126347, A278984, (row sums of A383713).

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, add(
      b(n-j, max(i, j)), j=1..min(n, i+1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..36);  # Alois P. Heinz, May 08 2025

PARI

A_x(N) = {my(x='x+O('x^(N+1))); Vec(1 + sum(i=1,(N/2)+1, x^(i*(i+1)/2)/prod(j=1,i, 1 - (x-x^(j+1))/(1-x))))}
A_x(40)

Formula

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