login
A273903
Triangle read by rows: T(n,k) is the number of bargraphs of semiperimeter n having k even-length columns (n>=2,k>=0).
3
1, 1, 1, 2, 2, 1, 4, 6, 2, 1, 8, 14, 10, 2, 1, 16, 35, 28, 15, 2, 1, 33, 84, 88, 46, 21, 2, 1, 69, 203, 247, 176, 68, 28, 2, 1, 146, 486, 693, 558, 311, 94, 36, 2, 1, 312, 1163, 1882, 1786, 1083, 507, 124, 45, 2, 1, 673, 2776, 5052, 5410, 3898, 1900, 780, 158, 55, 2, 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) = A004149(n).
Sum(k*T(n,k),k>=0) = A273904(n).
LINKS
M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.
Emeric Deutsch, S Elizalde, Statistics on bargraphs viewed as cornerless Motzkin paths, arXiv preprint arXiv:1609.00088, 2016
FORMULA
G.f.: G = G(t,z) satisfies aG^2 + bG + c = 0, where a = z(tz^2-tz+z+t), b = tz^4+(1+t)z^3+(1-t)z^2+(1+t)z-1, c =tz^4+z^2.
The trivariate g.f. G(t,s,z), where t (s) marks number of odd-length (even-length) columns and z marks semiperimeter, satisfies AG^2 + BG + C = 0, where A = z(tsz^2-tsz+tz+s), B = tsz^4+(t+s)z^3+(1-ts)z^2+(t+s)z-1, C = tsz^4+s(1-t)z^3+tz^2.
EXAMPLE
Row 4 is 2,2,1 because the 5 (=A082582(4)) bargraphs of semiperimeter 4 correspond to the compositions [1,1,1],[1,2],[2,1],[2,2],[3] and, clearly, they have 0,1,1,2,0 columns of even length.
Triangle starts
1;
1,1;
2,2,1;
4,6,2,1;
8,14,10,2,1
MAPLE
eq := z*(t*z^2-t*z+z+t)*f^2-(1-(t+1)*z-(1-t)*z^2-(t+1)*z^3-t*z^4)*f+z^2+t*z^4 = 0: f := RootOf(eq, f): fser := simplify(series(f, z = 0, 15)): for n from 2 to 12 do P[n]:=sort(coeff(fser, z, n)) end do: for n from 2 to 12 do seq(coeff(P[n], t, k), k=0..n-2) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, y, t) option remember; expand(`if`(n=0, 1-t,
`if`(t<0, 0, b(n-1, y+1, 1))+ `if`(t>0 or y<2, 0,
b(n, y-1, -1))+ `if`(y<1, 0, b(n-1, y, 0)*z^
`if`(y::even, 1, 0))))
end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..n-2))(b(n, 0$2)):
seq(T(n), n=2..15); # Alois P. Heinz, Jun 24 2016
MATHEMATICA
b[n_, y_, t_] := b[n, y, t] = Expand[If[n == 0, 1 - t, If[t < 0, 0, b[n - 1, y + 1, 1]] + If[t > 0 || y < 2, 0, b[n, y - 1, -1]] + If[y < 1, 0, b[n - 1, y, 0]*z^If[EvenQ[y], 1, 0]]]];
T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, n-2}]][b[n, 0, 0] ];
Table[T[n], {n, 2, 15}] // Flatten (* Jean-François Alcover, Jul 21 2016, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jun 23 2016
STATUS
approved