A071943 Triangle T(n,k) (n>=0, 0 <= k <= n) read by rows giving number of underdiagonal lattice paths from (0,0) to (n,k) using only steps R=(1,0), V=(0,1) and D=(1,2).

1, 1, 1, 1, 2, 3, 1, 3, 7, 9, 1, 4, 12, 24, 31, 1, 5, 18, 46, 89, 113, 1, 6, 25, 76, 183, 342, 431, 1, 7, 33, 115, 323, 741, 1355, 1697, 1, 8, 42, 164, 520, 1376, 3054, 5492, 6847, 1, 9, 52, 224, 786, 2326, 5900, 12768, 22669, 28161, 1, 10, 63, 296, 1134, 3684, 10370

Offset

0,5

Comments

For another interpretation of this array see the Example section.

Links

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows 0 <= n <= 150, flattened)

James East, Nicholas Ham, Lattice paths and submonoids of Z^2, arXiv:1811.05735 [math.CO], 2018.

D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad J. Math., 49 (1997), 301-320.

N. J. A. Sloane, Rows 0 through 100

N. J. A. Sloane, Illustration of the initial terms of the U(n,k) array

Formula

G.f.=(1-q)/[z(2t+2t^2z-1+q)], where q=sqrt(1-4tz-4t^2z^2).

Define T(0,0)=1 and T(n,k)=0 for k<0 and k >n. Then the array is generated by the recurrence T(n,k) = T(n,k-1) + T(n-1,k) + T(n-1,k-2). For example, T(5,3) = 46 = T(5,2) + T(4,3) + T(4,1) = 18 + 24 + 4. - N. J. A. Sloane, Mar 28 2013

Example

T(3,2)=7 because we have RRRVV, RRVRV, RRVVR, RVRRV, RVRVR, RRD and RDR.
Array begins:
1,
1, 1,
1, 2, 3,
1, 3, 7, 9,
1, 4, 12, 24, 31,
1, 5, 18, 46, 89, 113,
1, 6, 25, 76, 183, 342, 431,
1, 7, 33, 115, 323, 741, 1355, 1697,
...
Equivalently, let U(n,k) (for n >= 0, 0 <= k <= n) be the number of walks from (0,0) to (n,k) using steps (1,1), (1,-1) and (0,-1). Then U(n,n-k) = T(n,k). The U(n,k) array begins:
4:  0  0  0  0  1  5 ...
3:  0  0  0  1  4 18 ...
2:  0  0  1  3 12 46 ...
1:  0  1  2  7 24 89 ...
0:  1  1  3  9 31 113 ...
-------------------------
k/n:0  1  2  3  4  5 ...
The recurrence for this version is: U(0,0)=1, U(n,k)=0 for k>n or k<0; U(n,k) = U(n,k+1) + U(n-1,k+1) + U(n,k-1). E.g. 46 = 18 + 4 + 24. Also U(n,0) = A052709(n-1).

Maple

U:=proc(n, k) option remember;
if (n < 0) then RETURN(0);
elif (n=0) then
   if (k=0) then RETURN(1); else RETURN(0); fi;
elif (k>n or k<0) then RETURN(0);
else RETURN(U(n, k+1)+U(n-1, k+1)+U(n-1, k-1));
fi;
end;
for n from 0 to 20 do
lprint( [seq(U(n, n-i), i=0..n)] );
od:

Mathematica

t[0, 0] = 1; t[n_, k_] /; k<0 || k>n = 0; t[n_, k_] := t[n, k] = t[n, k-1] + t[n-1, k] + t[n-1, k-2]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 07 2014, after N. J. A. Sloane *)

Crossrefs

Diagonal entries yield A052709. Row sums are A071356.

Related arrays: A071944, A071945, A071946.

Sequence in context: A208338 A236918 A152821 * A357329 A062869 A102473

Adjacent sequences: A071940 A071941 A071942 * A071944 A071945 A071946

Keyword

nonn,easy,tabl

Author

N. J. A. Sloane, Jun 15 2002

Extensions

Edited by Emeric Deutsch, Dec 21 2003

Edited by N. J. A. Sloane, Mar 28 2013

Status

approved