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.

1, 2, 2, 10, 16, 6, 70, 140, 90, 20, 588, 1344, 1134, 448, 70, 5544, 13860, 13860, 7392, 2100, 252, 56628, 151008, 169884, 109824, 42900, 9504, 924, 613470, 1717716, 2108106, 1561560, 750750, 231660, 42042, 3432, 6952660, 20225920, 26546520, 21781760, 12155000, 4667520, 1191190, 183040, 12870

Offset: 0

Author

Peter Luschny, Jan 19 2025

Keywords

• nonn
• tabl
• walk

Examples

			The triangle starts:
  [0] [      1]
  [1] [      2,        2]
  [2] [     10,       16,        6]
  [3] [     70,      140,       90,      20]
  [4] [    588,     1344,     1134,      448,       70]
  [5] [   5544,    13860,    13860,     7392,     2100,     252]
  [6] [  56628,   151008,   169884,   109824,    42900,    9504,     924]
  [7] [ 613470,  1717716,  2108106,  1561560,   750750,  231660,   42042,   3432]
  [8] [6952660, 20225920, 26546520, 21781760, 12155000, 4667520, 1191190, 183040, 12870]
.
For n = 2 the walks depending on the x-coordinate of the endpoint are:
W(x=0) = {NNSS,NSNS,NSWE,NWSE,NWES,WNSE,WNES,WWEE,WENS,WEWE},
W(x=1) = {NNSW,NNWS,NSNW,NSWN,NWNS,NWSN,NWWE,NWEW,WNNS,WNSN,WNWE,WNEW,WWNE,WWEN,WENW,WEWN},
W(x=2) = {NNWW,NWNW,NWWN,WNNW,WNWN,WWNN}.
		

Links

• M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008.
• Richard K. Guy, Christian Krattenthaler and Bruce E. Sagan, Lattice paths, reflections, & dimension-changing bijections, Ars Combin. 34 (1992), 3-15.

Crossrefs

Related triangles: A380120.

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

Programs

Python

from dataclasses import dataclass
@dataclass
class Walk: s: str = ""; x: int = 0; y: int = 0
def Trow(n: int) -> list[int]:
    W = [Walk()]
    row = [0] * (n + 1)
    for w in W:
        if len(w.s) == 2*n:
            if w.x == w.y: row[w.y] += 1
        else:
            for s in "NSWE":
                x = y = 0
                match s:
                    case "W": x =  1
                    case "E": x = -1
                    case "N": y =  1
                    case "S": y = -1
                    case _  : pass
                if (w.y + y >= 0) and (w.x + x >= 0):
                    W.append(Walk(w.s + s, w.x + x, w.y + y))
    return row
for n in range(6): print(Trow(n))