cp's OEIS Frontend

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

%I A380119 #14 Jan 21 2025 13:33:50
%S A380119 1,2,2,10,16,6,70,140,90,20,588,1344,1134,448,70,5544,13860,13860,
%T A380119 7392,2100,252,56628,151008,169884,109824,42900,9504,924,613470,
%U A380119 1717716,2108106,1561560,750750,231660,42042,3432,6952660,20225920,26546520,21781760,12155000,4667520,1191190,183040,12870
%N A380119 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 A380119 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 A380119 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 A380119 The triangle starts:
%e A380119   [0] [      1]
%e A380119   [1] [      2,        2]
%e A380119   [2] [     10,       16,        6]
%e A380119   [3] [     70,      140,       90,      20]
%e A380119   [4] [    588,     1344,     1134,      448,       70]
%e A380119   [5] [   5544,    13860,    13860,     7392,     2100,     252]
%e A380119   [6] [  56628,   151008,   169884,   109824,    42900,    9504,     924]
%e A380119   [7] [ 613470,  1717716,  2108106,  1561560,   750750,  231660,   42042,   3432]
%e A380119   [8] [6952660, 20225920, 26546520, 21781760, 12155000, 4667520, 1191190, 183040, 12870]
%e A380119 .
%e A380119 For n = 2 the walks depending on the x-coordinate of the endpoint are:
%e A380119 W(x=0) = {NNSS,NSNS,NSWE,NWSE,NWES,WNSE,WNES,WWEE,WENS,WEWE},
%e A380119 W(x=1) = {NNSW,NNWS,NSNW,NSWN,NWNS,NWSN,NWWE,NWEW,WNNS,WNSN,WNWE,WNEW,WWNE,WWEN,WENW,WEWN},
%e A380119 W(x=2) = {NNWW,NWNW,NWWN,WNNW,WNWN,WWNN}.
%o A380119 (Python)
%o A380119 from dataclasses import dataclass
%o A380119 @dataclass
%o A380119 class Walk: s: str = ""; x: int = 0; y: int = 0
%o A380119 def Trow(n: int) -> list[int]:
%o A380119     W = [Walk()]
%o A380119     row = [0] * (n + 1)
%o A380119     for w in W:
%o A380119         if len(w.s) == 2*n:
%o A380119             if w.x == w.y: row[w.y] += 1
%o A380119         else:
%o A380119             for s in "NSWE":
%o A380119                 x = y = 0
%o A380119                 match s:
%o A380119                     case "W": x =  1
%o A380119                     case "E": x = -1
%o A380119                     case "N": y =  1
%o A380119                     case "S": y = -1
%o A380119                     case _  : pass
%o A380119                 if (w.y + y >= 0) and (w.x + x >= 0):
%o A380119                     W.append(Walk(w.s + s, w.x + x, w.y + y))
%o A380119     return row
%o A380119 for n in range(6): print(Trow(n))
%Y A380119 Related triangles: A380120.
%Y A380119 Cf. A005568 (column 0), A000984 (main diagonal), A253487 (sub diagonal), A151403 (row sums).
%K A380119 nonn,tabl,walk
%O A380119 0,2
%A A380119 _Peter Luschny_, Jan 19 2025