login
A121468
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).
0
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, 7, 1, 1264, 742, 352, 149, 58, 21, 8, 1, 3582, 2151, 1041, 451, 181, 68, 24, 9, 1, 10092, 6177, 3038, 1340, 550, 213, 78, 27, 10, 1, 28291, 17600, 8772, 3925, 1639, 649, 245, 88, 30, 11, 1
OFFSET
1,2
COMMENTS
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).
LINKS
E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
E. Barcucci, R. Pinzani and R. Sprugnoli, Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.
E. Deutsch and H. Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.
FORMULA
T(n,k) = Sum(j*T(n-j,k),j=1..n-k)+k*fibonacci(2n-2k-1).
G.f. of column k: z^k*(1-z)^2*(1-3z+z^2-kz^2+kz)/(1-3z+z^2)^2.
EXAMPLE
Triangle starts:
1;
2,1;
6,3,1;
18,9,4,1;
53,28,12,5,1;
MAPLE
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
CROSSREFS
Sequence in context: A321331 A046803 A280789 * A168151 A213221 A180281
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Aug 03 2006
STATUS
approved