VOOZH about

URL: https://oeis.org/A378067

⇱ A378067 - OEIS

login
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.
3
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,3
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.
FORMULA
Sum_{k=1..n} T(n, k) = 2 * A378069(n).
EXAMPLE
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.
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
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))
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).
Sequence in context: A227418 A278447 A235590 * A069655 A353706 A004574
KEYWORD
nonn,tabl,walk
AUTHOR
Peter Luschny, Dec 08 2024
STATUS
approved