A238861 Compositions with superdiagonal growth: number of compositions (p0, p1, p2, ...) of n with pi - p0 >= i.

1, 1, 1, 2, 2, 3, 4, 6, 7, 10, 13, 18, 24, 32, 41, 55, 72, 95, 125, 164, 212, 275, 355, 459, 592, 763, 980, 1257, 1605, 2044, 2598, 3298, 4179, 5290, 6685, 8435, 10623, 13353, 16751, 20978, 26228, 32746, 40831, 50850, 63247, 78569, 97475, 120770, 149429, 184641, 227853, 280832, 345722, 425134, 522232, 640847, 785604

Offset

0,4

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..8000 (terms 0..1000 from Alois P. Heinz)

Formula

G.f.: 1 + sum(n>=1, q^(n*(n+1)/2) / ( (1-q)^(n-1) * (1-q^n) ) ). [Joerg Arndt, Mar 30 2014]

Example

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

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=i..n)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..60);  # Alois P. Heinz, Mar 26 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, i, n}]]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Feb 18 2015, after Alois P. Heinz *)

Prog

(PARI) N=66; q='q+O('q^N);
gf = 1 + sum(n=1, N, q^(n*(n+1)/2) / ( (1-q)^(n-1) * (1-q^n) ) );
v=Vec(gf) \\ Joerg Arndt, Mar 30 2014

Crossrefs

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

Cf. A238859 (compositions of n with subdiagonal growth), 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: A239833 A115593 A274312 * A309212 A320270 A274156

Adjacent sequences: A238858 A238859 A238860 * A238862 A238863 A238864

Keyword

nonn

Author

Joerg Arndt, Mar 24 2014

Status

approved