|
%I #15 Nov 26 2023 19:13:43
%S 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,
%T 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,
%U 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
%N 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)).
%C 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).
%C 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
%H Alois P. Heinz, <a href="/A129183/b129183.txt">Rows n = 0..50, flattened</a>
%H M. P. Delest and J. M. Fedou, <a href="http://dx.doi.org/10.1007/3-540-53101-7_4">Counting polyominoes using attribute grammars</a>, Lecture Notes in Computer Science, vol. 461, pp. 46-60, Springer, Berlin, 1990.
%H M. P. Delest and J. M. Fedou, <a href="http://dx.doi.org/10.1016/0304-3975(92)90380-X">Attribute grammars are useful for combinatorics</a>, Theor. Comp. Sci., 98, 1992, 65-76.
%H M. P. Delest and J. M. Fedou, <a href="http://dx.doi.org/10.1016/0012-365X(93)90224-H">Enumeration of skew Ferrers diagrams</a>, Discrete Mathematics. vol.112, no.1-3, pp. 65-79, (1993).
%F 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.
%e T(4,5) = 4 because we have UDUUDUDD, UUDUDDUD, UUDUUDDD and UUUDDUDD.
%e Triangle starts:
%e 1;
%e 0,1;
%e 0,0,2;
%e 0,0,0,4,1;
%e 0,0,0,0,8,4,2;
%e 0,0,0,0,0,16,12,9,4,1;
%p 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
%p # second Maple program:
%p b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
%p expand(b(x-1, y+1, 1)+ `if`(t=1, z^y, 1)*b(x-1, y-1, 0))))
%p end:
%p T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
%p seq(T(n), n=0..10); # _Alois P. Heinz_, Jun 10 2014
%t 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_ *)
%Y Cf. A000108, A011782, A000079, A000302.
%K nonn,tabf
%O 0,6
%A _Emeric Deutsch_, Apr 07 2007
|
