A121468 - OEIS

%I #8 Feb 14 2016 11:06:28

%S 1,2,1,6,3,1,18,9,4,1,53,28,12,5,1,154,85,38,15,6,1,443,253,117,48,18,

%T 7,1,1264,742,352,149,58,21,8,1,3582,2151,1041,451,181,68,24,9,1,

%U 10092,6177,3038,1340,550,213,78,27,10,1,28291,17600,8772,3925,1639,649,245,88,30,11,1

%N Triangle read by rows: T(n,k) is the number of k-cell columns in all directed column-convex polyominoes of area n (1<=k<=n).

%C Also number of ascents of length k in all nondecreasing Dyck paths of semilength n. A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing. Example: T(4,2)=9 because we have (UU)DD(UU)DD, (UU)DDUDUD, UD(UU)DDUD, UDUD(UU)DD, (UU)D(UU)DDD, (UU)DUDUDD, UD(UU)DUDD, where U=(1,1) and D=(1,-1); the ascents of length 2 are shown between parentheses; the other six nondecreasing Dyck paths of semilength 4 have no ascents of length 2. Sum of entries in row n = A038731(n-1). T(n,1)=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 T(n,k) = Sum(j*T(n-j,k),j=1..n-k)+k*fibonacci(2n-2k-1).

%F G.f. of column k: z^k*(1-z)^2*(1-3z+z^2-kz^2+kz)/(1-3z+z^2)^2.

%e Triangle starts:

%e 1;

%e 2,1;

%e 6,3,1;

%e 18,9,4,1;

%e 53,28,12,5,1;

%p F:=k->z^k*(1-z)^2*(1-3*z+z^2-k*z^2+k*z)/(1-3*z+z^2)^2: T:=(n,k)->coeff(series(F(k),z=0,25),z^n): for n from 1 to 12 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

%Y Cf. A038731, A094864.

%K nonn,tabl

%O 1,2

%A _Emeric Deutsch_, Aug 03 2006