login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 6
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 (list; table; graph; refs; listen; history; text; internal format)
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 * A062869 A102473 A011117

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 23 05:42 EDT 2021. Contains 343199 sequences. (Running on oeis4.)