A238859 Compositions with subdiagonal growth: number of compositions (p0, p1, p2, ...) of n with pi - p0 <= i.

1, 1, 2, 4, 7, 14, 26, 51, 99, 195, 383, 759, 1504, 2988, 5944, 11840, 23602, 47084, 93975, 187647, 374812, 748857, 1496487, 2991017, 5978900, 11952780, 23897506, 47782081, 95543378, 191053334, 382052880, 764019152, 1527898772, 3055572646, 6110782652, 12220980359

Offset

0,3

Links

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

Formula

a(n) ~ c * 2^n, where c = 1/2 - QPochhammer(1/2)/2 = 0.3556059524566987893605501390353846099555440475796571079426294669... - Vaclav Kotesovec, May 01 2014, updated Mar 17 2024

Example

There are a(6) = 26 such compositions of 6:
01:  [ 1 1 1 1 1 1 ]
02:  [ 1 1 1 1 2 ]
03:  [ 1 1 1 2 1 ]
04:  [ 1 1 1 3 ]
05:  [ 1 1 2 1 1 ]
06:  [ 1 1 2 2 ]
07:  [ 1 1 3 1 ]
08:  [ 1 2 1 1 1 ]
09:  [ 1 2 1 2 ]
10:  [ 1 2 2 1 ]
11:  [ 1 2 3 ]
12:  [ 2 1 1 1 1 ]
13:  [ 2 1 1 2 ]
14:  [ 2 1 2 1 ]
15:  [ 2 1 3 ]
16:  [ 2 2 1 1 ]
17:  [ 2 2 2 ]
18:  [ 2 3 1 ]
19:  [ 3 1 1 1 ]
20:  [ 3 1 2 ]
21:  [ 3 2 1 ]
22:  [ 3 3 ]
23:  [ 4 1 1 ]
24:  [ 4 2 ]
25:  [ 5 1 ]
26:  [ 6 ]

Maple

b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i=0, add(b(n-j, j+1), j=1..n),
       add(b(n-j, i+1), j=1..min(n, i))))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 25 2014

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i == 0, Sum[b[n-j, j+1], {j, 1, n}], Sum[ b[n-j, i+1], {j, 1, Min[n, i]}]]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 13 2015, after Alois P. Heinz *)

Crossrefs

Cf. A238860 (partitions with superdiagonal growth), A238861 (compositions with superdiagonal growth), A000009 (partitions into distinct parts have superdiagonal growth by definition).

Cf. A238876 (partitions with subdiagonal growth), A001227 (partitions into distinct parts with subdiagonal growth).

Cf. A008930 (subdiagonal compositions), A238875 (subdiagonal partitions), A010054 (subdiagonal partitions into distinct parts).

Cf. A219282 (superdiagonal compositions), A238873 (superdiagonal partitions), A238394 (strictly superdiagonal partitions), A238874 (strictly superdiagonal compositions), A025147 (strictly superdiagonal partitions into distinct parts).

Sequence in context: A280917 A052535 A027988 * A224960 A217933 A005594

Adjacent sequences: A238856 A238857 A238858 * A238860 A238861 A238862

Keyword

nonn

Author

Joerg Arndt, Mar 24 2014

Status

approved