OFFSET
1,2
COMMENTS
Also number of nondecreasing Dyck paths of semilength n and such that there are k positive differences in the sequence of the valley altitudes, preceded by a 0. Example: T(5,2)=1 because we have UUDUUDUDDD, where U=(1,1) and D=(1,-1) (the valleys are at the altitudes 1 and 2 with two "jumps" in the sequence 0,1,2).
Row n has ceiling(n/2) terms.
Row sums are the odd-subscripted Fibonacci numbers (A001519).
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
EXAMPLE
T(5,2)=1 because we have the directed column-convex polyomino [(0,2),(1,3),(2,3)] (here the j-th pair gives the lower and upper levels of the j-th column).
Triangle starts:
1;
2;
4, 1;
8, 5;
16, 17, 1;
32, 49, 8;
64, 129, 39, 1;
MAPLE
with(combinat): T:=(n, k)->add(2^j*binomial(n-k-2-j, k-1)*binomial(k+j, k), j=0..n-2*k-1): for n from 0 to 15 do seq(T(n, k), k=0..ceil(n/2)-1) od; # yields sequence in triangular form
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Aug 02 2006
STATUS
approved