1,2

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 ceil(n/2) terms. Row sums are the odd-subscripted Fibonacci numbers (A001519). T(n,0)=2^(n-1)=A000079(n-1). T(n,1)=1+(n-3)*2^(n-2)=A000337(n-2). T(n,2)=A055581(n-5). Sum(k*T(n,k),k=0..ceil(n/2)-1)=A001870(n-3).

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.

T(n,k)=Sum((2^j*binomial(n-k-2-j,k-1)*binomial(k+j,k),j=0..n-2*k-1) for k>=1; T(n,0)=2^(n-1) G.f.=G=G(t,z)=z(1-z)/(1-3z+2z^2-tz^2).

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;

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

Cf. A001519, A000079, A000337, A055581, A001870.

Sequence in context: A127529 A091977 A112829 this_sequence A065290 A065266 A065260

Adjacent sequences: A121463 A121464 A121465 this_sequence A121467 A121468 A121469

nonn,tabf

Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 02 2006