A378061 - OEIS

%I #19 Dec 08 2024 17:22:02

%S 1,0,1,3,0,1,0,8,0,1,20,0,15,0,1,0,75,0,24,0,1,175,0,189,0,35,0,1,0,

%T 784,0,392,0,48,0,1,1764,0,2352,0,720,0,63,0,1,0,8820,0,5760,0,1215,0,

%U 80,0,1,19404,0,29700,0,12375,0,1925,0,99,0,1

%N Triangle read by rows: T(n, k) = binomial(n + 1, (n - k)/2)^2*(k + 1)/(n + 1) if n - k is even, otherwise 0.

%C 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.

%H R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, sandsteps and Pascal pyramids</a>, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

%e Triangle starts:

%e   0  [   1]

%e   1  [   0,    1]

%e   2  [   3,    0,    1]

%e   3  [   0,    8,    0,    1]

%e   4  [  20,    0,   15,    0,   1]

%e   5  [   0,   75,    0,   24,   0,    1]

%e   6  [ 175,    0,  189,    0,  35,    0,  1]

%e   7  [   0,  784,    0,  392,   0,   48,  0,  1]

%e   8  [1764,    0, 2352,    0, 720,    0, 63,  0, 1]

%e   9  [   0, 8820,    0, 5760,   0, 1215,  0, 80, 0, 1]

%e .

%e 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'.

%p T := (n, k) -> ifelse((n - k)::odd, 0, binomial(n+1, (n-k)/2)^2*(k+1)/(n+1)):

%p for n from 0 to 9 do seq(T(n, k), k = 0..n) od;

%t 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 *)

%o (Python)

%o # Creates the table by counting the heights of square lattice walks. For illustration only.

%o from dataclasses import dataclass

%o @dataclass

%o class Z: w: str = ""; r: int = 0; i: int = 0

%o def Trow(n: int) -> list[int]:

%o     W = [Z()]

%o     row = [0] * (n + 1)

%o     for x in W:

%o         if len(x.w) == n:

%o             if x.r == 0: row[x.i] += 1

%o         else:

%o             for s in "NSWE":

%o                 r = i = 0

%o                 match s:

%o                     case "W": r = 1

%o                     case "E": r = -1

%o                     case "N": i = 1

%o                     case "S": i = -1

%o                 if x.i + i >= 0:

%o                     W.append(Z(x.w + s, x.r + r, x.i + i))

%o     return row

%o for n in range(10): print(f"[{n}] {Trow(n)}")

%Y The columns are aerated rows of A378062. See also: A000891, A145600, A145601, A145602, A145603.

%Y Cf. A018224 (row sums), A378060.

%K nonn,tabl,new

%O 0,4

%A _Peter Luschny_, Dec 07 2024