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

Author

Joerg Arndt, Mar 24 2014

Keywords

• nonn

Examples

			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 ]
		

Links

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

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

Programs

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

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