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

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, 784, 0, 392, 0, 48, 0, 1, 1764, 0, 2352, 0, 720, 0, 63, 0, 1, 0, 8820, 0, 5760, 0, 1215, 0, 80, 0, 1, 19404, 0, 29700, 0, 12375, 0, 1925, 0, 99, 0, 1

Offset: 0

Author

Peter Luschny, Dec 07 2024

Keywords

• nonn
• tabl

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.

Examples

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

Links

• R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

Crossrefs

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

Cf. A018224 (row sums), A378060.

Programs

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

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)}")