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,2

Links

Table of n, a(n) for n=0..44.

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.

Example

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

Prog

(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))

Crossrefs

Related triangles: A380120.

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

Sequence in context: A307538 A316200 A360636 * A362745 A179789 A334396

Adjacent sequences: A380116 A380117 A380118 * A380120 A380121 A380122

Keyword

nonn,tabl,walk

Author

Peter Luschny, Jan 19 2025

Status

approved