A108439 Triangle read by rows: T(n,k) is 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 having abscissa of first return equal to 3k.

2, 4, 6, 20, 12, 34, 132, 60, 68, 238, 996, 396, 340, 476, 1858, 8132, 2988, 2244, 2380, 3716, 15510, 69940, 24396, 16932, 15708, 18580, 31020, 135490, 624132, 209820, 138244, 118524, 122628, 155100, 270980, 1223134, 5725124, 1872396, 1188980

Offset

1,1

Comments

Row sums yield A027307. T(n,n) = A108424(n).

Links

Table of n, a(n) for n=1..39.

Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Formula

G.f.: tzA(z)A(tz)+tzA(z)A^2(tz), where A=1+zA^2+zA^3=(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).

T(n, k) = A108424(k)*A027307(n-k) (there are explicit formulas in A108424 and A027307).

Example

T(2,1)=4 because we have u(d)ud, u(d)Udd, Ud(d)ud and Ud(d)Udd, the d step of the first return being shown between parentheses.
Triangle begins:
2;
4,6;
20,12,34;
132,60,68,238;
...

Maple

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

Crossrefs

Cf. A027307, A108424, A108435.

Sequence in context: A185185 A234019 A279188 * A245766 A193774 A241210

Adjacent sequences: A108436 A108437 A108438 * A108440 A108441 A108442

Keyword

nonn,tabl

Author

Emeric Deutsch, Jun 05 2005

Status

approved