OFFSET
1,2
REFERENCES
E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202.
FORMULA
T(n, 1)=sum(c(i), i=0..n-1), T(n, k)=sum(c(j)*binomial(n-1-j, k-1)*binomial(n-1-j, k)/(n-1-j), j=0..n-2) for k>1, where c(i)=binomial(2i, i)/(i+1) (i=0, 1, ...) are the Catalan numbers (A000108);
G.f.=1+tzC(z)[1+r(t, z)], where C(z)=1+zC(z)^2 is the Catalan function and r(t, z)=z[1+r(t, z)][1+tr(t, z)] is the Narayana function.
EXAMPLE
T(4,2)=4 because we have U(UD)(UD)D|UD, U(UD)U(UD)DD|, UU(UD)D(UD)D| and
UU(UD)(UD)DD|, where U=(1,1), D=(1,-1) (the peaks before the first return | are shown between parentheses).
1
2
4 1
9 4 1
23 11 7 1
65 27 28 11 1
197 66 87 62 16 1
626 170 239 250 122 22 1
2056 471 627 829 630 219 29 1
6918 1398 1656 2448 2553 1419 366 37 1
23714 4381 4554 6803 8813 6979 2917 578 46 1
82500 14282 13231 18571 27362 28364 17206 5567 872 56 1
MAPLE
c:=n->binomial(2*n, n)/(n+1):
T:=proc(n, k) if k=1 then sum(c(i), i=0..n-1) else sum(c(j)*binomial(n-1-j, k-1)*binomial(n-1-j, k)/(n-1-j), j=0..n-2) fi end proc:
T(1, 1);
for n from 1 to 12 do seq(T(n, k), k=1..n-1) od; # yields the sequence in triangular form
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Dec 22 2004
STATUS
approved