A380119 - OEIS

%I #14 Jan 21 2025 13:33:50

%S 1,2,2,10,16,6,70,140,90,20,588,1344,1134,448,70,5544,13860,13860,

%T 7392,2100,252,56628,151008,169884,109824,42900,9504,924,613470,

%U 1717716,2108106,1561560,750750,231660,42042,3432,6952660,20225920,26546520,21781760,12155000,4667520,1191190,183040,12870

%N Triangle read by rows: T(n, k) is the number of walks of length 2*n on the N X N grid with unit steps in all four directions (NSWE) starting at (0, 0). k is the common value of the x- and the y-coordinate of the endpoint of the walk.

%H M. Bousquet-Mélou and M. Mishna, <a href="https://doi.org/10.48550/arXiv.0810.4387">Walks with small steps in the quarter plane</a>, arXiv:0810.4387 [math.CO], 2008.

%H Richard K. Guy, Christian Krattenthaler and Bruce E. Sagan, <a href="http://www.mat.univie.ac.at/~kratt/artikel/paths.html">Lattice paths, reflections, & dimension-changing bijections</a>, Ars Combin. 34 (1992), 3-15.

%e The triangle starts:

%e   [0] [      1]

%e   [1] [      2,        2]

%e   [2] [     10,       16,        6]

%e   [3] [     70,      140,       90,      20]

%e   [4] [    588,     1344,     1134,      448,       70]

%e   [5] [   5544,    13860,    13860,     7392,     2100,     252]

%e   [6] [  56628,   151008,   169884,   109824,    42900,    9504,     924]

%e   [7] [ 613470,  1717716,  2108106,  1561560,   750750,  231660,   42042,   3432]

%e   [8] [6952660, 20225920, 26546520, 21781760, 12155000, 4667520, 1191190, 183040, 12870]

%e .

%e For n = 2 the walks depending on the x-coordinate of the endpoint are:

%e W(x=0) = {NNSS,NSNS,NSWE,NWSE,NWES,WNSE,WNES,WWEE,WENS,WEWE},

%e W(x=1) = {NNSW,NNWS,NSNW,NSWN,NWNS,NWSN,NWWE,NWEW,WNNS,WNSN,WNWE,WNEW,WWNE,WWEN,WENW,WEWN},

%e W(x=2) = {NNWW,NWNW,NWWN,WNNW,WNWN,WWNN}.

%o (Python)

%o from dataclasses import dataclass

%o @dataclass

%o class Walk: s: str = ""; x: int = 0; y: int = 0

%o def Trow(n: int) -> list[int]:

%o     W = [Walk()]

%o     row = [0] * (n + 1)

%o     for w in W:

%o         if len(w.s) == 2*n:

%o             if w.x == w.y: row[w.y] += 1

%o         else:

%o             for s in "NSWE":

%o                 x = y = 0

%o                 match s:

%o                     case "W": x =  1

%o                     case "E": x = -1

%o                     case "N": y =  1

%o                     case "S": y = -1

%o                     case _  : pass

%o                 if (w.y + y >= 0) and (w.x + x >= 0):

%o                     W.append(Walk(w.s + s, w.x + x, w.y + y))

%o     return row

%o for n in range(6): print(Trow(n))

%Y Related triangles: A380120.

%Y Cf. A005568 (column 0), A000984 (main diagonal), A253487 (sub diagonal), A151403 (row sums).

%K nonn,tabl,walk

%O 0,2

%A _Peter Luschny_, Jan 19 2025