|
%I #9 Jan 30 2023 05:55:06
%S 1,0,1,1,0,1,1,3,0,1,3,4,5,0,1,6,13,7,7,0,1,14,28,27,10,9,0,1,31,70,
%T 62,45,13,11,0,1,70,164,171,108,67,16,13,0,1,157,392,429,325,166,93,
%U 19,15,0,1,353,926,1101,862,540,236,123,22,17,0,1,793,2189,2766,2355,1499,824
%N Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n having k 1-cell columns (0<=k<=n).
%C Also number of nondecreasing Dyck paths of semilength n and such that there are k ascents of length 1. A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing. Example: T(4,2)=5 because we have (U)D(U)DUUDD, (U)DUUDD(U)D, (U)DUUD(U)DD, UUDD(U)D(U)D and UUD(U)D(U)DD, where U=(1,1) and D=(1,-1); the ascents of length one are shown between parentheses (also the Dyck path UUDUDDUD has two ascents but it is not nondecreasing because the valleys have altitudes 1 and 0). Row sums are the odd-subscripted Fibonacci numbers (A001519). T(n,0)=A006356(n-3). Sum(k*T(n,k),k=0..n)=A094864(n-1).
%H E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, <a href="http://dx.doi.org/10.1016/S0012-365X(97)82778-1">Nondecreasing Dyck paths and q-Fibonacci numbers</a>, Discrete Math., 170, 1997, 211-217.
%H E. Barcucci, R. Pinzani and R. Sprugnoli, <a href="http://dx.doi.org/10.1007/3-540-56610-4_71">Directed column-convex polyominoes by recurrence relations</a>, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.
%H E. Deutsch and H. Prodinger, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00222-6">A bijection between directed column-convex polyominoes and ordered trees of height at most three</a>, Theoretical Comp. Science, 307, 2003, 319-325.
%F G.f.: G(t,z)=(1-2z)/[1-(t+2)z+(2t-1)z^2-(t-1)z^3)].
%e T(3,1)=3 because we have the three directed column-convex polyominoes: [(0,2),(0,1)], [(0,2),(1,2)] and [(0,1),(0,2)] (here the j-th pair within the square brackets gives the lower and upper levels of the j-th column of that particular polyomino).
%e Triangle starts:
%e 1;
%e 0,1;
%e 1,0,1;
%e 1,3,0,1;
%e 3,4,5,0,1;
%e 6,13,7,7,0,1;
%p G:=(1-2*z)/(1-(t+2)*z+(2*t-1)*z^2-(t-1)*z^3): Gser:=simplify(series(G,z=0,16)): P[0]:=1: for n from 1 to 13 do P[n]:=sort(coeff(Gser,z,n)) od: for n from 0 to 13 do seq(coeff(P[n],t,j),j=0..n) od; # yields sequence in triangular form
%Y Cf. A001519 (row sums), A006356, A094864.
%K nonn,tabl
%O 0,8
%A _Emeric Deutsch_, Aug 03 2006
|
