|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
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
|
Table of n, a(n) for n=1..59.
|
|
|
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
|
Cf. A001519, A000295, A016777.
Sequence in context: A178216 A019213 A019128 * A115022 A177822 A091156
Adjacent sequences: A121460 A121461 A121462 * A121464 A121465 A121466
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
Emeric Deutsch, Jul 31 2006
|
|
|
STATUS
|
approved
|
| |
|
|
