|
Search: id:A121463
|
|
|
| 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, 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; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
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.
|
|
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: A062145 A019213 A019128 this_sequence A115022 A091156 A092288
Adjacent sequences: A121460 A121461 A121462 this_sequence A121464 A121465 A121466
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 31 2006
|
|
|
Search completed in 0.002 seconds
|
