cp's OEIS Frontend

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

%I A071943 #42 Jan 21 2019 11:50:01
%S A071943 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,
%T A071943 431,1,7,33,115,323,741,1355,1697,1,8,42,164,520,1376,3054,5492,6847,
%U A071943 1,9,52,224,786,2326,5900,12768,22669,28161,1,10,63,296,1134,3684,10370
%N 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).
%C A071943 For another interpretation of this array see the Example section.
%H A071943 Michael De Vlieger, <a href="/A071943/b071943.txt">Table of n, a(n) for n = 0..11475</a> (rows 0 <= n <= 150, flattened)
%H A071943 James East, Nicholas Ham, <a href="https://arxiv.org/abs/1811.05735">Lattice paths and submonoids of Z^2</a>, arXiv:1811.05735 [math.CO], 2018.
%H A071943 D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, <a href="http://dx.doi.org/10.4153/CJM-1997-015-x">On some alternative characterizations of Riordan arrays</a>, Canad J. Math., 49 (1997), 301-320.
%H A071943 N. J. A. Sloane, <a href="/A071943/a071943.txt">Rows 0 through 100</a>
%H A071943 N. J. A. Sloane, <a href="/A071943/a071943.pdf">Illustration of the initial terms of the U(n,k) array</a>
%F A071943 G.f.=(1-q)/[z(2t+2t^2z-1+q)], where q=sqrt(1-4tz-4t^2z^2).
%F A071943 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
%e A071943 T(3,2)=7 because we have RRRVV, RRVRV, RRVVR, RVRRV, RVRVR, RRD and RDR.
%e A071943 Array begins:
%e A071943 1,
%e A071943 1, 1,
%e A071943 1, 2, 3,
%e A071943 1, 3, 7, 9,
%e A071943 1, 4, 12, 24, 31,
%e A071943 1, 5, 18, 46, 89, 113,
%e A071943 1, 6, 25, 76, 183, 342, 431,
%e A071943 1, 7, 33, 115, 323, 741, 1355, 1697,
%e A071943 ...
%e A071943 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:
%e A071943 4:  0  0  0  0  1  5 ...
%e A071943 3:  0  0  0  1  4 18 ...
%e A071943 2:  0  0  1  3 12 46 ...
%e A071943 1:  0  1  2  7 24 89 ...
%e A071943 0:  1  1  3  9 31 113 ...
%e A071943 -------------------------
%e A071943 k/n:0  1  2  3  4  5 ...
%e A071943 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).
%p A071943 U:=proc(n,k) option remember;
%p A071943 if (n < 0) then RETURN(0);
%p A071943 elif (n=0) then
%p A071943    if (k=0) then RETURN(1); else RETURN(0); fi;
%p A071943 elif (k>n or k<0) then RETURN(0);
%p A071943 else RETURN(U(n,k+1)+U(n-1,k+1)+U(n-1,k-1));
%p A071943 fi;
%p A071943 end;
%p A071943 for n from 0 to 20 do
%p A071943 lprint( [seq(U(n,n-i),i=0..n)] );
%p A071943 od:
%t A071943 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_ *)
%Y A071943 Diagonal entries yield A052709. Row sums are A071356.
%Y A071943 Related arrays: A071944, A071945, A071946.
%K A071943 nonn,easy,tabl
%O A071943 0,5
%A A071943 _N. J. A. Sloane_, Jun 15 2002
%E A071943 Edited by _Emeric Deutsch_, Dec 21 2003
%E A071943 Edited by _N. J. A. Sloane_, Mar 28 2013