A380120 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). k is the absolute value of the x-coordinate of the endpoint of the walk.

1, 2, 2, 6, 8, 2, 20, 30, 12, 2, 70, 112, 56, 16, 2, 252, 420, 240, 90, 20, 2, 924, 1584, 990, 440, 132, 24, 2, 3432, 6006, 4004, 2002, 728, 182, 28, 2, 12870, 22880, 16016, 8736, 3640, 1120, 240, 32, 2, 48620, 87516, 63648, 37128, 17136, 6120, 1632, 306, 36, 2

Offset: 0

Author

Peter Luschny, Jan 17 2025

Keywords

• nonn
• tabl
• walk

Examples

			Triangle starts:
  [0] [    1]
  [1] [    2,     2]
  [2] [    6,     8,     2]
  [3] [   20,    30,    12,     2]
  [4] [   70,   112,    56,    16,     2]
  [5] [  252,   420,   240,    90,    20,    2]
  [6] [  924,  1584,   990,   440,   132,   24,    2]
  [7] [ 3432,  6006,  4004,  2002,   728,  182,   28,   2]
  [8] [12870, 22880, 16016,  8736,  3640, 1120,  240,  32,  2]
  [9] [48620, 87516, 63648, 37128, 17136, 6120, 1632, 306, 36, 2]
.
For n = 0 there is only the empty walk w = '' with start and end point (x=0, y=0).
For n = 3 the walks depending on the x-coordinate of the endpoint are:
W(x= 3) = {WWW},
W(x= 2) = {NWW,SWW,WNW,WSW,WWN,WWS},
W(x= 1) = {NNW,NSW,NWN,NWS,SNW,SSW,SWN,SWS,WNN,WNS,WSN,WSS,WWE,WEW,EWW},
W(x= 0) = {NNN,NNS,NSN,NSS,NWE,NEW,SNN,SNS,SSN,SSS,SWE,SEW,WNE,WSE,WEN,WES,ENW,ESW,EWN,EWS},
W(x=-1) = {NNE,NSE,NEN,NES,SNE,SSE,SEN,SES,WEE,ENN,ENS,ESN,ESS,EWE,EEW},
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=-1)) = 30,
T(3, 2) = card(W(x=2)) + card(W(x=-2)) = 12, T(3, 3) = card(W(x=3)) + card(W(x=-3)) = 2.
		

Links

• 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 (N X N), A378067 (Z X N), A379822 (Z X Z, variant), A380119.

Cf. A000984 (column 0), A162551 (column 1), A006659 (column 2), A000302 (row sums), A068551 (row sum without column 0), A040000 (row minimum).

Programs

Maple

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

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[abs(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) if k = 0, otherwise 2*binomial(2*n, n - k).

Assuming the columns starting at n = 0, i.e. prepended by k zeros:

T(n, k) = [x^n] (2^(2*k+1)*x^k / (sqrt(1-4*x)*(1+sqrt(1-4*x))^(2*k))) for k >= 1.

T(n, k) = n! * [x^n] (2*BesselI(k, 2*x)*exp(2*x)) for k >= 1.