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

%I #15 Mar 17 2024 10:04:54

%S 1,1,2,4,7,14,26,51,99,195,383,759,1504,2988,5944,11840,23602,47084,

%T 93975,187647,374812,748857,1496487,2991017,5978900,11952780,23897506,

%U 47782081,95543378,191053334,382052880,764019152,1527898772,3055572646,6110782652,12220980359

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

%H Alois P. Heinz, <a href="/A238859/b238859.txt">Table of n, a(n) for n = 0..1000</a>

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

%e There are a(6) = 26 such compositions of 6:

%e 01: [ 1 1 1 1 1 1 ]

%e 02: [ 1 1 1 1 2 ]

%e 03: [ 1 1 1 2 1 ]

%e 04: [ 1 1 1 3 ]

%e 05: [ 1 1 2 1 1 ]

%e 06: [ 1 1 2 2 ]

%e 07: [ 1 1 3 1 ]

%e 08: [ 1 2 1 1 1 ]

%e 09: [ 1 2 1 2 ]

%e 10: [ 1 2 2 1 ]

%e 11: [ 1 2 3 ]

%e 12: [ 2 1 1 1 1 ]

%e 13: [ 2 1 1 2 ]

%e 14: [ 2 1 2 1 ]

%e 15: [ 2 1 3 ]

%e 16: [ 2 2 1 1 ]

%e 17: [ 2 2 2 ]

%e 18: [ 2 3 1 ]

%e 19: [ 3 1 1 1 ]

%e 20: [ 3 1 2 ]

%e 21: [ 3 2 1 ]

%e 22: [ 3 3 ]

%e 23: [ 4 1 1 ]

%e 24: [ 4 2 ]

%e 25: [ 5 1 ]

%e 26: [ 6 ]

%p b:= proc(n, i) option remember; `if`(n=0, 1,

%p `if`(i=0, add(b(n-j, j+1), j=1..n),

%p add(b(n-j, i+1), j=1..min(n,i))))

%p end:

%p a:= n-> b(n, 0):

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Mar 25 2014

%t 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_ *)

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

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

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

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

%K nonn

%O 0,3

%A _Joerg Arndt_, Mar 24 2014