A273349 Triangle read by rows: T(n,k) is the number of bargraphs of semiperimeter n having k level steps (n>=2,k>=0). A level step in a bargraph is any pair of adjacent horizontal steps at the same height.

1, 1, 1, 3, 1, 1, 6, 5, 1, 1, 14, 12, 7, 1, 1, 33, 34, 19, 9, 1, 1, 79, 95, 61, 27, 11, 1, 1, 194, 261, 193, 95, 36, 13, 1, 1, 482, 728, 585, 333, 136, 46, 15, 1, 1, 1214, 2022, 1797, 1091, 521, 184, 57, 17, 1, 1, 3090, 5634, 5439, 3629, 1821, 763, 239, 69, 19, 1, 1

Offset

2,4

Comments

Number of entries in row n is n-1.

Sum of entries in row n = A082582(n).

T(n,0) = A025243(n+1).

Sum(k*T(n,k),k>=0) = A271943(n-1). This implies that the number of level steps in all bargraphs of semiperimeter n is equal to the sum of the widths of all bargraphs of semiperimeter n-1.

References

A. Blecher, C. Brennan, and A. Knopfmacher, Combinatorial parameters in bargraphs (preprint).

Links

Alois P. Heinz, Rows n = 2..150, flattened

M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.

Formula

G.f.: G(t,z) = (1-tz-z-2z^2+tz^2-sqrt((1-z)(1-z-2tz-4z^2+t^2z^2+2tz^2-4z^3-t^2z^3+4tz^3)))/(2z) (z marks semiperimeter, t marks level steps; obtained from the expression for F in the Blecher et al. reference (Section 7.1) by setting x=z, y=z, w=t).

Example

Row 4 is 3,1,1 because the 5 (=A082582(4)) bargraphs of semiperimeter 4 correspond to the compositions [1,1,1], [1,2], [2,1], [2,2], [3] which, clearly, have 2,0,0,1,0 level steps.
Triangle starts
1;
1,1;
3,1,1;
6,5,1,1;
14,12,7,1,1

Maple

G:=((1-t*z-z-2*z^2+t*z^2-sqrt((1-t*z-z-2*z^2+t*z^2)^2-4*z^3))*(1/2))/z: Gser:=simplify(series(G, z=0, 21)): for n from 2 to 18 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 2 to 18 do seq(coeff(P[n], t, j), j = 0 .. n-2) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, y, t, w) option remember; expand(
      `if`(n=0, (1-t), `if`(t<0, 0, b(n-1, y+1, 1, 0))+
      `if`(t>0 or y<2, 0, b(n, y-1, -1, 0))+ `if`(y<1, 0,
      `if`(w=1, z, 1)*b(n-1, y, 0, min(w+1, 1)))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0$3)):
seq(T(n), n=2..18);  # Alois P. Heinz, Jun 04 2016

Mathematica

b[n_, y_, t_, w_] := b[n, y, t, w] = Expand[If[n == 0, 1 - t, If[t < 0, 0, b[n - 1, y + 1, 1, 0]] + If[t > 0 || y < 2, 0, b[n, y - 1, -1, 0]] + If[y < 1, 0, If[w == 1, z, 1]*b[n - 1, y, 0, Min[w + 1, 1]]]]];
T[n_] := Function [p, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][ b[n, 0, 0, 0]];
Table[T[n], {n, 2, 18}] // Flatten (* Jean-François Alcover, Jul 29 2016, after Alois P. Heinz *)

Crossrefs

Cf. A025243, A082582, A271943.

Sequence in context: A370174 A278132 A203950 * A159572 A190907 A035582

Adjacent sequences: A273346 A273347 A273348 * A273350 A273351 A273352

Keyword

nonn,tabl

Author

Emeric Deutsch, Jun 03 2016

Status

approved