A219282 Number of superdiagonal bargraphs with area n.

1, 1, 1, 2, 3, 4, 6, 9, 13, 18, 25, 35, 49, 68, 93, 126, 170, 229, 308, 413, 551, 731, 965, 1269, 1664, 2177, 2842, 3701, 4806, 6222, 8031, 10337, 13272, 17003, 21740, 27745, 35343, 44936, 57021, 72213, 91274, 115149, 145010, 182309, 228841, 286819, 358964, 448614, 559857, 697694

Offset: 0

Author

Joerg Arndt, Dec 04 2012

Keywords

• nonn

Comments

Number of compositions n = p(1) + p(2) + ... + p(m) such that p(k) >= k (superdiagonal compositions), see example. - Joerg Arndt, Dec 19 2012

Number of (n-2)-bit binary strings in which the runs of ones are successively (1, 11, 111, 1111, ...), as in for example 00101100111011110011111000... To turn such a string into a composition, add 'X0 to the start of the empty string and the mark ' to the end, replace the runs 1, 11, 111,... with '01, '011, '0111, ... then consider the distances between the marks. - Andrew Woods, Jan 02 2015

Examples

			From _Joerg Arndt_, Dec 19 2012: (Start)
The a(9) = 18 compositions 9 = p(1) + p(2) + ... + p(m) such that p(k) >= k are
[ 1]  [ 1 2 6 ]
[ 2]  [ 1 3 5 ]
[ 3]  [ 1 4 4 ]
[ 4]  [ 1 5 3 ]
[ 5]  [ 1 8 ]
[ 6]  [ 2 2 5 ]
[ 7]  [ 2 3 4 ]
[ 8]  [ 2 4 3 ]
[ 9]  [ 2 7 ]
[10]  [ 3 2 4 ]
[11]  [ 3 3 3 ]
[12]  [ 3 6 ]
[13]  [ 4 2 3 ]
[14]  [ 4 5 ]
[15]  [ 5 4 ]
[16]  [ 6 3 ]
[17]  [ 7 2 ]
[18]  [ 9 ]
(End)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from Vincenzo Librandi)
• Margaret Archibald, Aubrey Blecher, Arnold Knopfmacher, and Stephan Wagner, Subdiagonal and superdiagonal compositions, Art Disc. Appl. Math. (2024). See p. 10.
• Emeric Deutsch, Emanuele Munarini, and Simone Rinaldi, Skew Dyck paths, area, and superdiagonal bargraphs, Journal of Statistical Planning and Inference, Vol. 140, Issue 6, June 2010, pp. 1550-1562.

Crossrefs

Cf. A063978 (compositions such that p(k) >= k-1 for k >= 2).

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

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

Cf. A098131 (compositions with smallest part >= number of parts; g.f. Sum_{k>=0} x^(k^2)/(1-x)^k).

Cf. A143862 (compositions with every part divisible by number of parts; g.f. Sum_{k>=0} x^(k^2) / (1 - x^k)^k).

Cf. A238860 (partitions with superdiagonal growth), A238861 (compositions 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).

Row sums of A305556.

Programs

Maple

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

Mathematica

nmax = 50; CoefficientList[Series[Sum[x^(k*(k+1)/2) / (1-x)^k, {k, 0, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Jan 05 2015 *)
b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, i+1], {j, i, n}]]; a[n_] := b[n, 1]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Mar 24 2015, after Alois P. Heinz *)

PARI

N=66; q='q+O('q^N);
gf=sum(n=0,N, q^(n*(n+1)/2) / (1-q)^n );
v=Vec(gf)

Formula

G.f.: Sum_{n>=0} q^(n*(n+1)/2) / (1-q)^n.

a(n) = Sum_{k=0..floor((sqrt(8*n+1)-3)/2)} C(n-1-C(k+1,2),k), for n >= 1.