A129183 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n such that the sum of the height of the peaks is k (n>=0; n<=k<=floor((n+1)^2/4)).

1, 0, 1, 0, 0, 2, 0, 0, 0, 4, 1, 0, 0, 0, 0, 8, 4, 2, 0, 0, 0, 0, 0, 16, 12, 9, 4, 1, 0, 0, 0, 0, 0, 0, 32, 32, 30, 20, 12, 4, 2, 0, 0, 0, 0, 0, 0, 0, 64, 80, 88, 73, 56, 34, 20, 9, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 128, 192, 240, 232, 206, 156, 116, 72, 46, 24, 12, 4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset

0,6

Comments

Row n has 1+floor((n+1)^2/4) terms, the first n of which are equal to 0. Row sums yield the Catalan numbers (A000108). T(n,n) = 2^(n-1) = A011782(n) = A000079(n-1) for n>=1. Sum(k*T(n,k), k>=0) = 4^(n-1) = A000302(n-1).

Also number of parallelogram polyominoes of semiperimeter n+1 and having area equal to k. Example: T(3,4)=1 because the square with side 2 is the only parallelogram polyomino with semiperimeter 4 and area 4. - Emeric Deutsch, Apr 07 2007

Links

Alois P. Heinz, Rows n = 0..50, flattened

M. P. Delest and J. M. Fedou, Counting polyominoes using attribute grammars, Lecture Notes in Computer Science, vol. 461, pp. 46-60, Springer, Berlin, 1990.

M. P. Delest and J. M. Fedou, Attribute grammars are useful for combinatorics, Theor. Comp. Sci., 98, 1992, 65-76.

M. P. Delest and J. M. Fedou, Enumeration of skew Ferrers diagrams, Discrete Mathematics. vol.112, no.1-3, pp. 65-79, (1993).

Formula

G.f.: G(t,z)=H(t,1,z), where H(t,x,z)=1+z*(H(t,t*x,z)-1+t*x)*H(t,x,z) where H(t,x,z) is the trivariate g.f. for Dyck paths according to sum of the height of the peaks, number of peaks and semilength, marked by t,x and z, respectively.

Example

T(4,5) = 4 because we have UDUUDUDD, UUDUDDUD, UUDUUDDD and UUUDDUDD.
Triangle starts:
1;
0,1;
0,0,2;
0,0,0,4,1;
0,0,0,0,8,4,2;
0,0,0,0,0,16,12,9,4,1;

Maple

H:=1/(1-z*h[1]+z-z*t*x): for n from 1 to 11 do h[n]:=1/(1-z*h[n+1]+z-z*t^(n+1)*x) od: h[12]:=0: x:=1: G:=simplify(H): Gser:=simplify(series(G, z=0, 11)): for n from 0 to 9 do P[n]:=sort(coeff(Gser, z, n)) od: for n from 0 to 9 do seq(coeff(P[n], t, j), j=0..floor((n+1)^2/4)) od; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
      expand(b(x-1, y+1, 1)+ `if`(t=1, z^y, 1)*b(x-1, y-1, 0))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
seq(T(n), n=0..10);  # Alois P. Heinz, Jun 10 2014

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y+1, 1] + If[t == 1, z^y, 1]*b[x-1, y-1, 0]]]]; T[n_] := Function[{p}, Table[ Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 0]]; Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, May 26 2015, after Alois P. Heinz *)

Crossrefs

Cf. A000108, A011782, A000079, A000302.

Sequence in context: A190608 A011991 A234931 * A280292 A181566 A348513

Adjacent sequences: A129180 A129181 A129182 * A129184 A129185 A129186

Keyword

nonn,tabf

Author

Emeric Deutsch, Apr 07 2007

Status

approved