login
A121463
Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n, having k distinct valley levels (n>=1, k>=0).
0
1, 1, 1, 1, 4, 1, 11, 1, 1, 26, 7, 1, 57, 30, 1, 1, 120, 102, 10, 1, 247, 303, 58, 1, 1, 502, 825, 256, 13, 1, 1013, 2116, 955, 95, 1, 1, 2036, 5200, 3178, 515, 16, 1, 4083, 12381, 9740, 2310, 141, 1, 1, 8178, 28779, 28064, 9078, 906, 19, 1, 16369, 65658, 77093
OFFSET
1,5
COMMENTS
Row n has 1+floor(n/2) terms. Row sums are the odd-subscripted Fibonacci numbers (A001519). T(n,0)=1; T(n,1)=2^n-n-1=A000295(n) (the Eulerian numbers). T(2n+1,n)=3n+1=A016777(n). T(2n,n)=1.
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