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

%I #42 Jan 21 2019 11:50:01

%S 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 431,1,7,33,115,323,741,1355,1697,1,8,42,164,520,1376,3054,5492,6847,

%U 1,9,52,224,786,2326,5900,12768,22669,28161,1,10,63,296,1134,3684,10370

%N 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 For another interpretation of this array see the Example section.

%H Michael De Vlieger, <a href="/A071943/b071943.txt">Table of n, a(n) for n = 0..11475</a> (rows 0 <= n <= 150, flattened)

%H 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 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 N. J. A. Sloane, <a href="/A071943/a071943.txt">Rows 0 through 100</a>

%H N. J. A. Sloane, <a href="/A071943/a071943.pdf">Illustration of the initial terms of the U(n,k) array</a>

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

%F 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 T(3,2)=7 because we have RRRVV, RRVRV, RRVVR, RVRRV, RVRVR, RRD and RDR.

%e Array begins:

%e 1,

%e 1, 1,

%e 1, 2, 3,

%e 1, 3, 7, 9,

%e 1, 4, 12, 24, 31,

%e 1, 5, 18, 46, 89, 113,

%e 1, 6, 25, 76, 183, 342, 431,

%e 1, 7, 33, 115, 323, 741, 1355, 1697,

%e ...

%e 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 4: 0 0 0 0 1 5 ...

%e 3: 0 0 0 1 4 18 ...

%e 2: 0 0 1 3 12 46 ...

%e 1: 0 1 2 7 24 89 ...

%e 0: 1 1 3 9 31 113 ...

%e -------------------------

%e k/n:0 1 2 3 4 5 ...

%e 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 U:=proc(n,k) option remember;

%p if (n < 0) then RETURN(0);

%p elif (n=0) then

%p if (k=0) then RETURN(1); else RETURN(0); fi;

%p elif (k>n or k<0) then RETURN(0);

%p else RETURN(U(n,k+1)+U(n-1,k+1)+U(n-1,k-1));

%p fi;

%p end;

%p for n from 0 to 20 do

%p lprint( [seq(U(n,n-i),i=0..n)] );

%p od:

%t 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 Diagonal entries yield A052709. Row sums are A071356.

%Y Related arrays: A071944, A071945, A071946.

%K nonn,easy,tabl

%O 0,5

%A _N. J. A. Sloane_, Jun 15 2002

%E Edited by _Emeric Deutsch_, Dec 21 2003

%E Edited by _N. J. A. Sloane_, Mar 28 2013