A108435 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 have k returns to the x-axis.

2, 6, 4, 34, 24, 8, 238, 172, 72, 16, 1858, 1360, 624, 192, 32, 15510, 11444, 5520, 1952, 480, 64, 135490, 100520, 50040, 19136, 5600, 1152, 128, 1223134, 911068, 463512, 186416, 60320, 15168, 2688, 256, 11320066, 8457504, 4371808, 1821312, 629440, 178176, 39424, 6144, 512

Offset: 1

Author

Emeric Deutsch, Jun 04 2005

Keywords

• nonn
• tabl

Comments

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.

Examples

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

Links

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

Crossrefs

Cf. A027307, A108424, A108436.

Programs

Maple

T:=proc(n,k) if k
				

Mathematica

T[n_, k_] := Which[k < n, (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}]), k == n, 2^n, True, 0];
Table[T[n, k], {n, 1, 9}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 11 2024, after Maple code. *)

Formula

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

Extensions

Keyword tabf changed to tabl by Michel Marcus, Apr 09 2013