login
Number of superdiagonal bargraphs with area n.
32

%I #66 Feb 17 2024 11:20:19

%S 1,1,1,2,3,4,6,9,13,18,25,35,49,68,93,126,170,229,308,413,551,731,965,

%T 1269,1664,2177,2842,3701,4806,6222,8031,10337,13272,17003,21740,

%U 27745,35343,44936,57021,72213,91274,115149,145010,182309,228841,286819,358964,448614,559857,697694

%N Number of superdiagonal bargraphs with area n.

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

%C 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

%H Alois P. Heinz, <a href="/A219282/b219282.txt">Table of n, a(n) for n = 0..1000</a> (first 201 terms from Vincenzo Librandi)

%H Margaret Archibald, Aubrey Blecher, Arnold Knopfmacher, and Stephan Wagner, <a href="https://doi.org/10.26493/2590-9770.1675.fe8">Subdiagonal and superdiagonal compositions</a>, Art Disc. Appl. Math. (2024). See p. 10.

%H Emeric Deutsch, Emanuele Munarini, and Simone Rinaldi, <a href="http://dx.doi.org/10.1016/j.jspi.2009.12.013">Skew Dyck paths, area, and superdiagonal bargraphs</a>, Journal of Statistical Planning and Inference, Vol. 140, Issue 6, June 2010, pp. 1550-1562.

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

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

%e From _Joerg Arndt_, Dec 19 2012: (Start)

%e The a(9) = 18 compositions 9 = p(1) + p(2) + ... + p(m) such that p(k) >= k are

%e [ 1] [ 1 2 6 ]

%e [ 2] [ 1 3 5 ]

%e [ 3] [ 1 4 4 ]

%e [ 4] [ 1 5 3 ]

%e [ 5] [ 1 8 ]

%e [ 6] [ 2 2 5 ]

%e [ 7] [ 2 3 4 ]

%e [ 8] [ 2 4 3 ]

%e [ 9] [ 2 7 ]

%e [10] [ 3 2 4 ]

%e [11] [ 3 3 3 ]

%e [12] [ 3 6 ]

%e [13] [ 4 2 3 ]

%e [14] [ 4 5 ]

%e [15] [ 5 4 ]

%e [16] [ 6 3 ]

%e [17] [ 7 2 ]

%e [18] [ 9 ]

%e (End)

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

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

%p end:

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

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

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

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

%o (PARI)

%o N=66; q='q+O('q^N);

%o gf=sum(n=0,N, q^(n*(n+1)/2) / (1-q)^n );

%o v=Vec(gf)

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

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

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

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

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

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

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

%Y Row sums of A305556.

%K nonn

%O 0,4

%A _Joerg Arndt_, Dec 04 2012