A378067 Triangle read by rows: T(n, k) is the number of walks of length n with unit steps in all four directions (NSWE) starting at (0, 0), staying in the upper plane (y >= 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, 1, 2, 4, 3, 3, 9, 10, 6, 10, 36, 25, 20, 20, 25, 100, 101, 55, 50, 55, 101, 400, 301, 231, 126, 126, 231, 301, 1225, 1226, 742, 490, 294, 490, 742, 1226, 4900, 3921, 3144, 1632, 1008, 1008, 1632, 3144, 3921, 15876, 15877, 10593, 7137, 3348, 2592, 3348, 7137, 10593, 15877

Offset: 0

Author

Peter Luschny, Dec 08 2024

Keywords

• nonn
• tabl
• walk

Examples

			Triangle starts:
  [0] [    1]
  [1] [    1,     2]
  [2] [    4,     3,     3]
  [3] [    9,    10,     6,   10]
  [4] [   36,    25,    20,   20,   25]
  [5] [  100,   101,    55,   50,   55,  101]
  [6] [  400,   301,   231,  126,  126,  231,  301]
  [7] [ 1225,  1226,   742,  490,  294,  490,  742, 1226]
  [8] [ 4900,  3921,  3144, 1632, 1008, 1008, 1632, 3144,  3921]
  [9] [15876, 15877, 10593, 7137, 3348, 2592, 3348, 7137, 10593, 15877]
.
For n = 3 we get the walks depending on the x-coordinate of the endpoint:
W(x= 3) = {WWW},
W(x= 2) = {NWW,WNW,WWN},
W(x= 1) = {NNW,NSW,NWN,NWS,WWE,WEW,EWW,WNN,WNS},
W(x= 0) = {NNN,NNS,NSN,NWE,NEW,WNE,WEN,ENW,EWN},
W(x=-1) = {NNE,NEN,ENN,NSE,NES,WEE,ENS,EWE,EEW},
W(x=-2) = {NEE,ENE,EEN},
W(x=-3) = {EEE}.
T(3, 0) = card(W(x=0)) = 9, T(3, 1) = card(W(x=1)) + card(W(x=-3)) = 10,
T(3, 2) = card(W(x=2)) + card(W(x=-2)) = 6, T(3, 3) = card(W(x=3)) + card(W(x=-1)) = 10.
		

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 (first quadrant), this triangle (upper plane), A379822 (whole plane).

Cf. A018224 (column 0), A001700 (row sums), A378069 (row sum without column 0), A380121 (row minimum).

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

Formula

Sum_{k=1..n} T(n, k) = 2 * A378069(n).