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
Examples
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).
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
Crossrefs
Programs
-
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 *)
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
Extensions
Edited by Emeric Deutsch, Dec 21 2003
Edited by N. J. A. Sloane, Mar 28 2013
Comments