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

Author

Emeric Deutsch, Jun 05 2005

Keywords

• nonn
• tabl

Comments

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

Examples

			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;
...
		

Links

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

Crossrefs

Cf. A027307, A108424, A108435.

Programs

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

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).