A379822 Triangle read by rows: T(n, k) is the number of walks of length n on the Z X Z grid with unit steps in all four directions (NSWE) starting at (0, 0), and ending on the vertical line x = 0 if k = 0, or on the line x = k or x = -(n + 1 - k) if k > 0.

1, 2, 2, 6, 5, 5, 20, 16, 12, 16, 70, 57, 36, 36, 57, 252, 211, 130, 90, 130, 211, 924, 793, 507, 286, 286, 507, 793, 3432, 3004, 2016, 1092, 728, 1092, 2016, 3004, 12870, 11441, 8024, 4488, 2380, 2380, 4488, 8024, 11441, 48620, 43759, 31842, 18717, 9384, 6120, 9384, 18717, 31842, 43759

Offset: 0

Author

Peter Luschny, Jan 16 2025

Keywords

• nonn
• tabl
• walk

Examples

			  [0] [    1]
  [1] [    2,     2]
  [2] [    6,     5,     5]
  [3] [   20,    16,    12,    16]
  [4] [   70,    57,    36,    36,   57]
  [5] [  252,   211,   130,    90,  130,  211]
  [6] [  924,   793,   507,   286,  286,  507,  793]
  [7] [ 3432,  3004,  2016,  1092,  728, 1092, 2016,  3004]
  [8] [12870, 11441,  8024,  4488, 2380, 2380, 4488,  8024, 11441]
  [9] [48620, 43759, 31842, 18717, 9384, 6120, 9384, 18717, 31842, 43759]
.
For n = 3 we get the walks depending on the x-coordinate of the endpoint:
W(x= 3) = {WWW},
W(x= 2) = {NWW,WWN,WNW,SWW,WSW,WWS},
W(x= 1) = {NNW,NWN,WNN,NSW,NWS,SWN,SNW,WWE,WEW,EWW,WNS,WSN,SWS,SSW,WSS},
W(x= 0) = {NNN,NNS,NSN,NWE,NEW,SNN,EWN,WNE,WEN,ENW,SNS,SSN,SWE,SEW,WSE,WES,ESW,EWS,NSS,SSS},
W(x=-1) = {NNE,ENN,NEN,NSE,NES,SNE,SEN,WEE,ENS,ESN,EWE,EEW,SSE,SES,ESS},
W(x=-2) = {NEE,SEE,ENE,ESE,EEN,EES},
W(x=-3) = {EEE}.
T(3, 0) = card(W(x=0)) = 20, T(3, 1) = card(W(x=1)) + card(W(x=-3)) = 16,
T(3, 2) = card(W(x=2)) + card(W(x=-2)) = 12, T(3, 3) = card(W(x=3)) + card(W(x=-1)) = 16.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 0..11475 (rows 0..150 of triangle, flattened).
• Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Séminaire de Combinatoire Philippe Flajolet, Institut Henri Poincaré, March 28, 2013.
• Alin Bostan and Manuel Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009; Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AK, (FPSAC 2009).
• R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

Crossrefs

Related triangles: A052174 (first quadrant), A378067 (upper plane), this triangle (whole plane).

Cf. A000984 (column 0), A323229 (column 1 and main diagonal), A000302 (row sums), A068551 (row sum without column 0), A283799 (row minimum).

Programs

Maple

T := (n, k) -> binomial(2*n, n - k) + binomial(2*n, k - 1):
seq(print(seq(T(n, k), k = 0..n)), n = 0..9);

Mathematica

A379822[n_, k_] := Binomial[2*n, n - k] + Binomial[2*n, k - 1];
Table[A379822[n, k], {n, 0, 10}, {k, 0, n}] (* Paolo Xausa, May 29 2025 *)

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) == n:
            row[w.x] += 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
                W.append(Walk(w.s + s, w.x + x, w.y + y))
    return row
for n in range(10): print(Trow(n))

Formula

T(n, k) = binomial(2*n, n - k) + binomial(2*n, k - 1).

Sum_{k=1..n} T(n, k) = A068551(n).