OFFSET
1,5
COMMENTS
REFERENCES
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.
LINKS
E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
FORMULA
T(n,k)=Sum(binomial(n,2*k+j)*binomial(k-1+j,k-1),j=0..n-2*k) (k<=n/2). G.f.=G=G(t,z)=(1-2z)/(1-3z+2z^2-tz^2)-1.
EXAMPLE
T(5,2)=7 because we have UDUDUUDUDD, UDUUDUDUDD, UDUUDUUDDD, UDUUUDDUDD, UUDDUUDUDD with valleys at levels 0 and 2, UDUUUDUDDD with valleys at levels 0 and 2 and UUDUUDUDDD with valleys at levels 1 and 2.
Triangle starts:
1;
1,1;
1,4;
1,11,1;
1,26,7;
1,57,30,1;
MAPLE
T:=(n, k)->sum(binomial(n, 2*k+j)*binomial(k-1+j, k-1), j=0..n-2*k): for n from 1 to 16 do seq(T(n, k), k=0..floor(n/2)) od; # yields sequence in triangular form
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jul 31 2006
STATUS
approved