1,1

Number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have k steps up to the first peak. Example: T(2,2)=4 because we have uudd, uUddd, Uuddd and UUdddd. Row sums yield A027307. T(n,1)=A108424(n). T(n,n)=2^n.

Problem 10658, American Math. Monthly, 107, 2000, 368-370.

T(n, k)=[k/(n-k)][3*2^k*binomial(n-1, k)+sum(2^(n-1-j)*(5n-2k+j+1)binomial(n-1, j)binomial(2n-k-1, n+j)/(n+j+1), j=0..n-k-2)] if k<n; T(n, n)=2^n. G.f. =1/(1-tzA-tzA^2)-1, where A=1+zA^2+zA^3 or, equivalently, A=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3 (the g.f. of A027307).

Example T(2,2)=4 because u(d)u(d), u(d)Ud(d), Ud(d)u(d) and Ud(d)Ud(d) (the steps d that return to the x-axis are shown between parentheses).

Triangle begins:

2;

6,4;

34,24,8;

238,172,72,16;

1858,1360,624,192,32;

T:=proc(n, k) if k<n then (k/(n-k))*(3*2^k*binomial(n-1, k)+sum(2^(n-1-j)*(5*n-2*k+j+1)*binomial(n-1, j)*binomial(2*n-k-1, n+j)/(n+j+1), j=0..n-k-2)) elif k=n then 2^n else 0 fi end: for n from 1 to 9 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form

Cf. A027307, A108424, A108436.

Sequence in context: A064538 A002790 A108951 this_sequence A126262 A080499 A072513

Adjacent sequences: A108432 A108433 A108434 this_sequence A108436 A108437 A108438

nonn,tabf

Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 04 2005