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,4

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.

Links

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

Formula

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

Example

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

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

Prog

(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)

Crossrefs

Row sums of A383713.

Cf. A000110, A011782, A047998, A107429, A126347, A278984.

Sequence in context: A255071 A103285 A000049 * A000050 A050253 A198518

Adjacent sequences: A383250 A383251 A383252 * A383254 A383255 A383256

Keyword

nonn,easy

Author

John Tyler Rascoe, May 06 2025

Status

approved