OFFSET
0,4
COMMENTS
Consider square lattice walks with unit steps in all four directions (NSWE), starting at the origin, ending on the y-axis, and never going below the x-axis. T(n, k) is the number of walks with length n and height k. The number of walks with positive height is A378060, and with nonnegative height is A018224. Walks of odd length can never have an even height, and walks of even length cannot have an odd height. The Python program below generates the walks.
LINKS
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
EXAMPLE
Triangle starts:
0 [ 1]
1 [ 0, 1]
2 [ 3, 0, 1]
3 [ 0, 8, 0, 1]
4 [ 20, 0, 15, 0, 1]
5 [ 0, 75, 0, 24, 0, 1]
6 [ 175, 0, 189, 0, 35, 0, 1]
7 [ 0, 784, 0, 392, 0, 48, 0, 1]
8 [1764, 0, 2352, 0, 720, 0, 63, 0, 1]
9 [ 0, 8820, 0, 5760, 0, 1215, 0, 80, 0, 1]
.
The 15 walks with length 4 and height 2 are: 'NNNS', 'NNSN', 'NNWE', 'NNEW', 'NSNN', 'NWNE', 'NWEN', 'NENW', 'NEWN', 'WNNE', 'WNEN', 'WENN', 'ENNW', 'ENWN', 'EWNN'.
MAPLE
T := (n, k) -> ifelse((n - k)::odd, 0, binomial(n+1, (n-k)/2)^2*(k+1)/(n+1)):
for n from 0 to 9 do seq(T(n, k), k = 0..n) od;
MATHEMATICA
T[n_, k_] := If[EvenQ[n-k], Binomial[n + 1, (n - k)/2]^2*(k + 1)/(n + 1), 0]; Table[T[n, k], {n, 0, 10}, {k, 0, n}]//Flatten (* Stefano Spezia, Dec 08 2024 *)
PROG
(Python)
# Creates the table by counting the heights of square lattice walks. For illustration only.
from dataclasses import dataclass
@dataclass
class Z: w: str = ""; r: int = 0; i: int = 0
def Trow(n: int) -> list[int]:
W = [Z()]
row = [0] * (n + 1)
for x in W:
if len(x.w) == n:
if x.r == 0: row[x.i] += 1
else:
for s in "NSWE":
r = i = 0
match s:
case "W": r = 1
case "E": r = -1
case "N": i = 1
case "S": i = -1
if x.i + i >= 0:
W.append(Z(x.w + s, x.r + r, x.i + i))
return row
for n in range(10): print(f"[{n}] {Trow(n)}")
CROSSREFS
KEYWORD
AUTHOR
Peter Luschny, Dec 07 2024
STATUS
approved