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

Links

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

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

Formula

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

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

Example

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

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

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

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

Sequence in context: A275142 A200226 A300628 * A115255 A055924 A286278

Adjacent sequences: A379819 A379820 A379821 * A379823 A379824 A379825

Keyword

nonn,tabl,walk

Author

Peter Luschny, Jan 16 2025

Status

approved